#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
#define y1 YONE
#define free freeee
#define lcm llcm
typedef unsigned long long ull;
using namespace std;
const int N=1e6+5,M=1e6+3;
int a[N],n,p,mx,b[N];
multiset<int> seg[4*N+5];
void build(int x,int l,int r){
for (int i=l;i<=r;i++) seg[x].ep(a[i]);
if (l==r) return;
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
return;
}
void edit(int x,int l,int r,int i,int val){
seg[x].erase(seg[x].find(val));
seg[x].ep(val+1);
if (l==r) return;
int mid=(l+r)/2;
if (i<=mid) edit(x*2,l,mid,i,val);
else edit(x*2+1,mid+1,r,i,val);
return;
}
int query(int x,int l,int r,int lx,int rx,int val){
if (l>rx || r<lx) return INT_MAX;
if (l>=lx && r<=rx) return *seg[x].upper_bound(val);
int mid=(l+r)/2;
return min(query(x*2,l,mid,lx,rx,val),query(x*2+1,mid+1,r,lx,rx,val));
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
if (a[i]<=mx) continue;
p=i;
mx=a[i];
}
for (int i=1;i<=p;i++) b[i]=max(b[i-1],a[i]);
for (int i=n;i>=p;i--) b[i]=max(b[i+1],a[i]);
set<pair<int,int>> s;
for (int i=1;i<=n;i++) if (a[i]!=b[i]) s.ep({a[i],i});
build(1,1,n);
int ans=0;
while (!s.empty()){
pair<int,int> x=*s.begin();
s.erase(x);
int l=query(1,1,n,1,x.S-1,x.F),r=query(1,1,n,x.S+1,n,x.F);
ans=(ans+x.F+l+r)%M;
edit(1,1,n,x.S,x.F);
a[x.S]++;
if (a[x.S]!=b[x.S]) s.ep({a[x.S],x.S});
}cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
188156 KB |
Output is correct |
2 |
Correct |
64 ms |
188088 KB |
Output is correct |
3 |
Incorrect |
64 ms |
188320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |