Submission #1282981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282981		thuhienne	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	2398 ms	86920 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 9;
const int mod = 1e6 + 3;
const int inf = 1e9 + 9;
//mod operator
int add(int x,int y) {
	x += y;
	if (x >= mod) x %= mod;
	return x;
}
int mul(long long x,int y) {
	x *= y;
	if (x >= mod) x %= mod;
	return x;
}
int subtract(int x,int y) {
	return add(x,mod - y);
}
int power(int x,int y) {
	if (y == 0) return 1;
	if (y % 2 == 0) {
		int a = power(x,y / 2);
		return mul(a,a);
	} else {
		int a = power(x,y - 1);
		return mul(a,x);
	}
}

#define re exit(0);

int n,h[maxn],desire[maxn],maxheight;

struct ev {
	int height,pos,val;
} event[maxn * 2];

int st[maxn * 4];

void build(int id,int l,int r) {
	if (l == r) {
		st[id] = h[l];
		return;
	}
	int mid = (l + r) >> 1;
	
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	
	st[id] = min(st[id*2],st[id*2+1]);
}
void update(int id,int l,int r,int pos,int val) {
	if (l > pos || r < pos) return;
	if (l == r) {
		st[id] = val;
		return;
	}
	int mid = (l + r) >> 1;
	
	update(id*2,l,mid,pos,val);
	update(id*2+1,mid+1,r,pos,val);
	
	st[id] = min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v) {
	if (l > v || r < u) return inf;
	if (l >= u && r <= v) return st[id];
	int mid = (l + r) >> 1;
	
	return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}

set <int> online;

long long sum(int l,int r) {
	return 1ll*(r + l)*(r - l + 1)/2;
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> h[i];
	maxheight = *max_element(h + 1,h + 1 + n);
	
	int pt;
	for (pt = 1;pt <= n;pt++) {
		if (h[pt] == maxheight) break;
		desire[pt] = max(desire[pt - 1],h[pt]);
	}
	int pt2;
	for (pt2 = n;pt2 >= 1;pt2--) {
		if (h[pt2] == maxheight) break;
		desire[pt2] = max(desire[pt2 + 1],h[pt2]);
	}
	for (int i = pt;i <= pt2;i++) desire[i] = maxheight;
	
	for (int i = 1;i <= n;i++) {
		event[i] = {h[i],i,1};
		event[i + n] = {desire[i],i,-1};
	}
	sort(event + 1,event + 1 + 2*n,[] (ev a,ev b) {
		if (a.height != b.height) return a.height < b.height;
		return a.val > b.val;
	});
	
	build(1,1,n);
	
	int res = 0;
	
	for (int i = 1;i <= 2*n;i++) {
		int d = event[i].height;
		if (event[i].val == 1) {
			online.insert(event[i].pos);
			update(1,1,n,event[i].pos,inf);
		}
		else online.erase(event[i].pos);
		
		while (i < 2 * n && event[i + 1].height == d) {
			i++;
			if (event[i].val == 1) {
				online.insert(event[i].pos);
				update(1,1,n,event[i].pos,inf);
			}
			else online.erase(event[i].pos);
		}
		
		if (i == 2 * n) break;
		
		if (online.empty()) continue;
		
		int l = *online.begin(),r = *online.rbegin();
		int aim = event[i + 1].height,curr = d;
		
		
		long long FUCK = sum(curr,aim - 1);
		if (online.size() == 1) {
			int d1 = get(1,1,n,1,l - 1),d2 = get(1,1,n,r + 1,n);
			res = add(res,add( mul(add(d1,d2),aim - curr),FUCK%mod ));
			continue;
		}
		
		int fuckleft = get(1,1,n,1,l - 1),fuckright = get(1,1,n,r + 1,n);
		int fuckmid = get(1,1,n,l + 1,r - 1);
	
		//default cost
		res = add(res, mul(online.size() - 2 , add( mul(3,FUCK%mod) , mul(2,aim - curr) ) ) );
		
		//min raise left and right
		long long costleft = 2*FUCK + 1ll*(aim - curr)*(fuckleft + min(fuckmid,fuckright)) + sum(curr + 1,aim) + 1ll*(aim - curr)*fuckright;
		long long costright = 2*FUCK + 1ll*(aim - curr)*(min(fuckleft,fuckmid) + fuckright) + sum(curr + 1,aim) + 1ll*(aim - curr)*fuckleft;
	
		res = add(res,min(costleft,costright)%mod);
	}
	
	cout << res;
	
}

• 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