Submission #1232561
Source Code Expand
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<numeric>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(lli i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
lli f(lli l, lli L, lli R, lli r){
return (r-l+1)*(r-l)/2 - (r-R+1)*(r-R)/2 - (L-l+1)*(L-l)/2;
}
int main(void){
lli n; cin >> n;
vector<int> a(n), b(n+1), c;
rep(i, n){
cin >> a[i];
b[a[i]] = i+1;
}
c.push_back(0);
c.push_back(n+1);
lli ans = 0;
reg(i, 1, n){
int t = b[i];
auto itr = lower_bound(c.begin(), c.end(), t);
ans += f(*(itr-1), t-1, t, (*itr)-1) * i;
c.push_back(t);
sort(c.begin(), c.end());
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
ktyshmt |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1265 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
2048 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
TLE |
2103 ms |
2048 KB |
corner1 |
TLE |
2103 ms |
1920 KB |
corner2 |
AC |
1 ms |
256 KB |
corner3 |
TLE |
2103 ms |
1920 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
TLE |
2103 ms |
1920 KB |
maxrand1 |
TLE |
2103 ms |
1920 KB |
maxrand2 |
TLE |
2103 ms |
1920 KB |
rand0 |
AC |
2 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |