oj.uz

Submission #123575

# Submission time Handle Problem Language Result Execution time Memory
123575 2019-07-01T17:05:12 Z vex Sails (IOI07_sails) C++14
0 / 100
 360 ms 2392 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];
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>0)update(1,1,MAX,a[i].vis-less+1,a[i].vis);
		update(1,1,MAX,leq,leq+(a[i].br-less)-1);
	}
	
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 996 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 1340 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 2300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 360 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -