Submission #1163359

#TimeUsernameProblemLanguageResultExecution timeMemory
1163359LCJLYReal Mountains (CCO23_day1problem2)C++20
25 / 25
2545 ms282200 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<int,int>pii; typedef pair<pii,int>pi2; mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); inline int combine(int a, int b){ return min(a,b); } struct node{ int s,e,m; node *l,*r; int v; int lazyUpd; node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0){ if(s!=e){ l=new node(s,m); r=new node(m+1,e); } } void upd(int x, int y){ if(s==e){ v=y; return; } if(x<=m) l->upd(x,y); else r->upd(x,y); v=combine(l->v,r->v); } int query(int x, int y){ if(x<=s&&y>=e){ return v; } if(y<=m) return l->query(x,y); if(x>m) return r->query(x,y); return combine(l->query(x,m),r->query(m+1,y)); } }; const int mod=1e6+3; int mul(int a, int b){ a%=mod; b%=mod; return (a*b)%mod; } void solve(){ int n; cin >> n; int arr[n]; node st(0,n+5); pii maxi={-1,-1}; vector<int>dis; for(int x=0;x<n;x++){ cin >> arr[x]; st.upd(x,arr[x]); dis.push_back(arr[x]); maxi=max(maxi,{arr[x],x}); } int target[n]; int cur=0; for(int x=0;x<=maxi.second;x++){ cur=max(cur,arr[x]); target[x]=cur; } cur=0; for(int x=n-1;x>=maxi.second;x--){ cur=max(cur,arr[x]); target[x]=cur; } sort(dis.begin(),dis.end()); dis.resize(unique(dis.begin(),dis.end())-dis.begin()); vector<int>storage[n+5]; vector<int>storage2[n+5]; for(int x=0;x<n;x++){ int a=lower_bound(dis.begin(),dis.end(),arr[x])-dis.begin(); int b=lower_bound(dis.begin(),dis.end(),target[x])-dis.begin(); storage[a].push_back(x); storage2[b].push_back(x); } multiset<int>se; int counter=0; for(int x=0;x<n;x++){ //pull from previous if(se.size()==1){ int diff=dis[x]-dis[x-1]; int index=*se.begin(); int lft=st.query(0,index-1); int rgt=st.query(index+1,n-1); counter+=mul(lft+rgt,diff); counter%=mod; counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size()); counter%=mod; } else if(se.size()==2){ int diff=dis[x]-dis[x-1]; int index=*se.begin(); int index2=*prev(se.end()); int lft=st.query(0,index-1); int a=st.query(index+1,n-1); int rgt=st.query(index2+1,n-1); int b=st.query(0,index2-1); counter+=mul(lft+rgt,diff); counter%=mod; counter+=mul(min(a,b),diff); counter%=mod; counter+=(dis[x]+dis[x-1]+1)*diff/2; counter%=mod; counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size()); counter%=mod; } else if(se.size()>2){ int diff=dis[x]-dis[x-1]; int index=*se.begin(); int index2=*prev(se.end()); int lft=st.query(0,index-1); int a=st.query(index+1,n-1); int rgt=st.query(index2+1,n-1); int b=st.query(0,index2-1); counter+=mul(lft+rgt,diff); counter%=mod; counter+=mul(min(a,b),diff); counter%=mod; counter+=(dis[x]+dis[x-1]+1)*diff/2; counter%=mod; counter+=mul((dis[x]+dis[x-1]+1)*diff,se.size()-2); counter%=mod; counter+=mul((dis[x]-1+dis[x-1])*diff/2,se.size()); counter%=mod; } for(auto it:storage[x]){ st.upd(it,1e15); se.insert(it); } for(auto it:storage2[x]){ se.erase(se.find(it)); } } cout << counter; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t=1; //cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...