Submission #123790

#	Time	Username	Problem	Language	Result	Execution time	Memory
123790		vex	Sails (IOI07_sails)	C++14	100 / 100	365 ms	3320 KiB

sails

#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 / 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