Submission #289690

#	Time	Username	Problem	Language	Result	Execution time	Memory
289690		b00n0rp	Sails (IOI07_sails)	C++17	100 / 100	521 ms	3448 KiB

sails

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

#define pii pair<int,int>
#define F first
#define S second

pii a[100005];
int seg[200005];
int MX = 100001;
int n;
int pref[100005];

void upd(int pos,int val){
	pos += MX;
	seg[pos] = val;
	pos /= 2;
	while(pos){
		seg[pos] = min(seg[pos*2],seg[pos*2+1]);
		pos /= 2;
	}
}

int query(int l,int r){
	l += MX;
	r += MX+1;
	int res = 1000000000;
	while(l < r){
		if(l%2 == 1) res = min(res,seg[l++]);
		if(r%2 == 1) res = min(res,seg[--r]);
		l /= 2;
		r /= 2;
	}
	return res;
}

signed main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i].F >> a[i].S;
	}
	sort(a,a+n);
	for(int i = 0; i < n; i++){
		pref[a[i].F+1] --;
		pref[a[i].F-a[i].S+1]++;
		upd(a[i].F+1,pref[a[i].F+1]);
		upd(a[i].F-a[i].S+1,pref[a[i].F-a[i].S+1]);
		if(pref[a[i].F-a[i].S+1] != 1) continue;
		else{
			 int x = a[i].F-a[i].S+1;
			 int l0 = 1,r0 = MX,l,r,mid;
			 l = 1,r = x;
			 while(l <= r){
				 mid = (l+r)/2;
				 if(query(mid,x) < 0){
					 l0 = mid;
					 l = mid+1;
				 }
				 else{
					 r = mid-1;
				 }
			 }
			 l = x,r = MX;
			 while(l <= r){
				 mid = (l+r)/2;
				 if(query(x,mid) < 0){
					 r0 = mid;
					 r = mid-1;
				 }
				 else{
					 l = mid+1;
				 }
			 }
			 pref[x]--;
			 pref[r0]++;
			 pref[l0]++;
			 pref[l0+r0-x]--;
			 upd(x,pref[x]);
			 upd(r0,pref[r0]);
			 upd(l0,pref[l0]);
			 upd(l0+r0-x,pref[l0+r0-x]);
		}
	}
	long long ans = 0,cur = 0;
	for(int i = 0; i < MX; i++){
		cur += pref[i];
		ans += (cur*(cur-1))/2;
	}
	cout << ans << endl;
}

• Subtask 1: 5 / 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: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10