oj.uz

Submission #289690

# Submission time Handle Problem Language Result Execution time Memory
289690 2020-09-02T22:49:53 Z b00n0rp Sails (IOI07_sails) C++17
100 / 100
 521 ms 3448 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 8 ms 1536 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 888 KB Output is correct
2 Correct 123 ms 964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1296 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 1944 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 3056 KB Output is correct
2 Correct 332 ms 3192 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 3192 KB Output is correct
2 Correct 262 ms 2860 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 3448 KB Output is correct
2 Correct 266 ms 2552 KB Output is correct