Submission #1169336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169336		PlayVoltz	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	3626 ms	384276 KiB

Main

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int MOD = 1000003;

int n;
set<int> ss;

struct node{
	int s, e, m, val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=0;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int ind, int nv){
		if (s==e)val=nv;
		else{
			if (ind<=m)l->up(ind, nv);
			else r->up(ind, nv);
			val = min(l->val, r->val);
		}
	}
	int query(int left, int right){
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return min(l->query(left, m), r->query(m+1, right));
	}
}*st;

int calc(int a, int b){
	a%=MOD;
	b%=MOD;
	if (ss.empty())return 0;
	int res=(((st->query(1, *ss.begin()-1)%MOD+st->query(*(--ss.end())+1, n)%MOD)%MOD)*((b-a+MOD)%MOD))%MOD;
	if (ss.size()==1)return res;
	res=(res+(b*(b-a+MOD))%MOD+(((2*ss.size()-3)%MOD)*((b*(b+1)/2)%MOD-(a*(a+1)/2)%MOD+MOD))%MOD)%MOD;
	return (res+MOD)%MOD;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int ans=0, p=-1;
	cin>>n;
	st = new node(1, n);
	map<int, vector<int> > m, done;
	vector<int> vect(n+1), f(n+2, 0);
	pii mx=mp(0, 0);
	for (int i=1; i<=n; ++i)cin>>vect[i], st->up(i, vect[i]), m[vect[i]].pb(i), mx=max(mx, mp(vect[i], i));
	for (int i=1; i<=mx.se; ++i)f[i]=max(f[i-1], vect[i]);
	for (int i=n; i>=mx.se; --i)f[i]=max(f[i+1], vect[i]);
	for (int i=1; i<=n; ++i){
		ans=(ans+(f[i]*(f[i]-1)/2)%MOD-(vect[i]*(vect[i]-1)/2)%MOD+MOD)%MOD;
		done[f[i]].pb(i);
	}
	for (auto c:m){
		if (p!=-1)ans=(ans+calc(p, c.fi))%MOD;
		for (auto a:c.se)ss.insert(a), st->up(a, LLONG_MAX/2);
		for (auto a:done[c.fi])ss.erase(a);
		p=c.fi;
	}
	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