oj.uz

Submission #123790

# Submission time Handle Problem Language Result Execution time Memory
123790 2019-07-02T06:56:22 Z vex Sails (IOI07_sails) C++14
100 / 100
 365 ms 3320 KB 
#include <bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define vis first
#define br second
using namespace std;
 
int n;
pii a[maxn];
 
int tree[4*maxn]={0};
int query(int v,int l,int r,int x)
{
	if(l>r)return 0;
	if(l==r)return tree[v];
	
	int mid=(l+r)/2;
	if(x<=mid)return tree[v]+query(2*v,l,mid,x);
	else return tree[v]+query(2*v+1,mid+1,r,x);
}
void update(int v,int l,int r,int lt,int rt)
{
	if(l>r || lt>rt || lt>r || l>rt)return;
	if(lt<=l && r<=rt)tree[v]++;
	else
	{
		int mid=(l+r)/2;
		update(2*v,l,mid,lt,rt);
		update(2*v+1,mid+1,r,lt,rt);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i].vis>>a[i].br;
	
	sort(a,a+n);
	int MAX=a[n-1].vis;
	
	for(int i=0;i<n;i++)	
	{
		int tar=query(1,1,MAX,a[i].vis-a[i].br+1);
		
		int levo=1;
		int desno=a[i].vis;
		int less=a[i].vis+1;
		while(levo<=desno)
		{
			int mid=(levo+desno)/2;
			int num=query(1,1,MAX,mid);
			if(num<tar)
			{
				less=min(mid,less);
				desno=mid-1;
			}
			else levo=mid+1;
		}
		
		int leq=a[i].vis;
		levo=1;
		desno=a[i].vis;
		while(levo<=desno)
		{
			int mid=(levo+desno)/2;
			int num=query(1,1,MAX,mid);
			if(num<=tar)
			{
				leq=min(mid,less);
				desno=mid-1;
			}
			else levo=mid+1;
		}
		
		if(less<=a[i].vis)update(1,1,MAX,less,a[i].vis);
		update(1,1,MAX,leq,leq+(a[i].br-(a[i].vis-less+1))-1);
		
		/*for(int i=1;i<=MAX;i++)
		{
			long long www=query(1,1,MAX,i);
			cout<<www<<" ";
		}
		cout<<endl;*/
	}
	
	long long sol=0LL;
	for(int i=1;i<=MAX;i++)
	{
		long long www=query(1,1,MAX,i);
		sol+=www*(www-1)/2;
	}
	
	cout<<sol<<endl;
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 13 ms 1400 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 760 KB Output is correct
2 Correct 55 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1144 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 1744 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 2852 KB Output is correct
2 Correct 237 ms 2936 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 3140 KB Output is correct
2 Correct 168 ms 2696 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 3320 KB Output is correct
2 Correct 184 ms 2524 KB Output is correct