Submission #1150242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150242		emptypringlescan	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	2935 ms	219596 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long mod=1000003;
int n;
long long arr[1000005],ans;
struct node{
	int s,e,m;
	node *l,*r;
	long long val;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			val=min(l->val,r->val);
		}
		else val=arr[s];
	}
	void update(int S, long long V){
		if(s==e){
			val=V;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		val=min(l->val,r->val);
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return val;
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return min(l->query(S,m),r->query(m+1,E));
	}
} *root;
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    pair<long long,int> hei[n+1];
    for(int i=1; i<=n; i++) cin >> arr[i],hei[i]={arr[i],i};
    sort(hei+1,hei+n+1);
    root=new node(1,n);
    long long mx[2][n+2];
    mx[0][0]=0; mx[1][n+1]=0;
    for(int i=1; i<=n; i++) mx[0][i]=max(mx[0][i-1],arr[i]);
    for(int i=n; i>=1; i--) mx[1][i]=max(mx[1][i+1],arr[i]);
    vector<pair<pair<long long,long long>,int> > up;
    for(int i=1; i<=n; i++){
		long long grr=min(mx[0][i],mx[1][i]);
		if(grr>arr[i]){
			up.push_back({{arr[i],grr},i});
			ans+=(arr[i]+grr-1ll)*(grr-arr[i])/2ll%mod;
			ans%=mod;
		}
	}
	sort(up.begin(),up.end());
	int cnt=0;
	set<int> ind;
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
	for(int i=1; i<n; i++){
		root->update(hei[i].second,1e16);
		if(hei[i].first==hei[i+1].first) continue;
		while(cnt<(int)up.size()&&hei[i].first==up[cnt].first.first){
			ind.insert(up[cnt].second);
			pq.push({up[cnt].first.second,up[cnt].second});
			cnt++;
		}
		while(!pq.empty()&&pq.top().first==hei[i].first){
			int x=pq.top().second;
			pq.pop();
			ind.erase(x);
		}
		if(ind.empty()) continue;
		//cout << hei[i].first << '\n';
		long long once=0;
		once+=root->query(1,*ind.begin()-1);
		//cout << root->query(1,*ind.begin()-1) << ' ';
		once+=root->query(*(--ind.end())+1,n);
		//cout << root->query(*(--ind.end())+1,n) << ' ';;
		if((int)ind.size()>1){
			once+=root->val;
			//cout << root->val << ' ';
			ans+=(((int)ind.size()-2ll)*2ll+1ll)*((hei[i].first+1ll+hei[i+1].first)*(hei[i+1].first-hei[i].first)/2ll%mod)%mod;
			//cout << "grr " << (((int)ind.size()-2ll)*2ll+1ll)*((hei[i].first+1ll+hei[i+1].first)*(hei[i+1].first-hei[i].first)/2ll%mod)%mod << '\n';
			ans%=mod;
		}
		//cout << '\n';
		ans+=once*(hei[i+1].first-hei[i].first)%mod;
		ans%=mod;
		//cout << ans << '\n';
	}
	cout << ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 4 / 4