Submission #1220008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220008		cxijsijsjsyk	Sails (IOI07_sails)	C++20	65 / 100	124 ms	131072 KiB

sails

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
pair<int, int> stick[100005]; int maxh;

int st[400005]; int lz[400005];
void push(int p, int cl, int cr) {
	if (cl >= cr) return;
	st[p*2] += lz[p];
	st[p*2+1] += lz[p];
	lz[p*2] += lz[p];
	lz[p*2+1] += lz[p];
	lz[p] = 0;
}

void update(int ql, int qr, int v, int p=1, int cl=1, int cr=maxh) {
	if (ql <= cl && qr >= cr) {
		st[p]+=v; lz[p] += v; return;
	}
	push(p, cl, cr);
	int mid = (cl+cr)/2;
	if (ql <= mid) update(ql, qr, v, p*2, cl, mid);
	if (qr > mid) update(ql, qr, v, p*2+1, mid+1, cr);
	st[p] = min(st[p*2], st[p*2+1]);
}

int pquery(int x, int p=1, int cl=1, int cr=maxh) {
	if (cl == cr) return st[p];
	push(p, cl, cr);
	int mid = (cl+cr)/2;
	if (x <= mid) return pquery(x, p*2, cl, mid);
	else return pquery(x, p*2+1, mid+1, cr);
}

int walk(int x, int p=1, int cl=1, int cr=maxh) {
	// find first smaller than x
	if (cl == cr) return cl;
	push(p, cl, cr);
	int mid = (cl+cr)/2;
	if (st[p*2]<x) return walk(x, p*2, cl, mid);
	else return walk(x, p*2+1, mid+1, cr);
}

signed main() {
	int n; cin>>n;
	for (int i = 1; i <= n; i++) {
		cin>>stick[i].first>>stick[i].second;
		maxh = max(maxh, stick[i].first);
	}
	sort(stick+1, stick+n+1);
	
	for (int i = 1; i <= n; i++) {
		//cout<<stick[i].second<<endl;
		int hval = pquery(stick[i].first-stick[i].second+1);
		int finst = walk(hval+1);
		int nextdown = walk(hval);
		int aff = min(stick[i].first, nextdown-1)-(stick[i].first-stick[i].second+1);
		//cout<<"update " <<finst<<" "<<finst+aff<<endl;
		//cout<<"update "<<nextdown<<" "<<stick[i].first<<endl;
		 update(finst, finst+aff, 1);
		 update(nextdown, stick[i].first, 1);
		// for (int i = 1; i <= n; i++) {
			// cout<<pquery(i)<<" ";
		// }
		// cout<<endl;
	}
	int ans = 0;
	for (int i = 1; i <= maxh; i++) {
		int x = pquery(i);
		//cout<<x<<endl;
		ans += 0.5*(x-1)*x;
	}
	cout<<ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10