Submission #905778
Source Code Expand
/****** BISMILLAH HIR RAHMANIR RAHIM ******/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned int ul;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef map<string,string> mss;
typedef map<int, vector<int> > mvii;
typedef map<int, int> mii;
typedef queue <int> qi;
typedef map <int, vector<string> > mvis;
typedef map <string, vector<int> > mvsi;
typedef vector <string> vs;
typedef pair <int, int> pii;
// Order Statistic Tree
/* Special functions:
find_by_order(val) --> returns iterator to the kth largest element counting from 0
order_of_key(val) --> returns the number of items in a set that are strictly smaller than our item
*/
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define MP make_pair
#define SORT(a) sort (a.begin(), a.end())
#define REVERSE(a) reverse (a.begin(), a.end())
#define ALL(a) a.begin(), a.end()
#define PI acos(-1)
#define ms(x,y) memset (x, y, sizeof (x))
#define INF 2000000000
#define pb push_back
#define MAX 100002
#define debug cout<<"A"<<"\n"
#define prnt(a) cout<<a<<"\n"
#define mod 1000000007LL
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define FORr(i,a,b) for (int i=(a); i>=b; i--)
#define itrALL(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define lc ((node)<<1)
#define rc ((node)<<1|1)
#define VecPrnt(v) FOR(j,0,v.size()) cout<<v[j]<<" "; cout<<endl
#define endl "\n"
#define PrintPair(x) cout<<x.first<<" "<<x.second<<endl
#define ClearQ(x); while(!x.empty()) x.pop()
#define EPS 1e-9
/* Direction Array */
// int fx[]={1,-1,0,0};
// int fy[]={0,0,1,-1};
// int fx[]={0,0,1,-1,-1,1,-1,1};
// int fy[]={-1,1,0,0,1,1,-1,-1};
template <class T> inline T bigmod(T p,T e,T M)
{
ll ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
template <class T, class X> inline bool getbit(T a, X i) { T t=1; return ((a&(t<<i))>0);}
template <class T, class X> inline T setbit(T a, X i) { T t=1;return (a|(t<<i)); }
template <class T, class X> inline T resetbit(T a, X i) { T t=1;return (a&(~(t<<i)));}
inline ll getnum()
{
char c = getchar();
ll num,sign=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')sign=-1;
for(num=0;c>='0'&&c<='9';)
{
c-='0';
num = num*10+c;
c=getchar();
}
return num*sign;
}
inline ll power(ll a, ll b)
{
ll multiply=1;
FOR(i,0,b)
{
multiply*=a;
}
return multiply;
}
/****** END OF HEADER ******/
int n, a;
int pos[2*MAX];
int main()
{
// ios_base::sync_with_stdio(0);
// cin.tie(NULL); cout.tie(NULL);
// freopen("in.txt","r",stdin);
scanf("%d", &n);
FOR(i,1,n+1)
{
scanf("%d", &a);
pos[a]=i;
}
set<int> take; take.insert(0); take.insert(n+1);
ll ans=0;
FOR(i,1,n+1)
{
auto it=take.lower_bound(pos[i]);
ll r=*it;
it--;
ll l=*it;
ans+=(ll)i*(pos[i]-l)*(r-pos[i]);
take.insert(pos[i]);
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
sycamoreTree |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3589 Byte |
Status |
AC |
Exec Time |
124 ms |
Memory |
10368 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:125:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:129:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name |
Status |
Exec Time |
Memory |
corner0 |
AC |
117 ms |
10368 KB |
corner1 |
AC |
124 ms |
10368 KB |
corner2 |
AC |
3 ms |
256 KB |
corner3 |
AC |
80 ms |
10368 KB |
example0 |
AC |
3 ms |
256 KB |
example1 |
AC |
3 ms |
256 KB |
example2 |
AC |
3 ms |
256 KB |
maxrand0 |
AC |
121 ms |
10368 KB |
maxrand1 |
AC |
116 ms |
10368 KB |
maxrand2 |
AC |
115 ms |
10368 KB |
rand0 |
AC |
3 ms |
256 KB |
rand1 |
AC |
3 ms |
256 KB |
rand2 |
AC |
3 ms |
256 KB |