Submission #292825

#	Time	Username	Problem	Language	Result	Execution time	Memory
292825		kshitij_sodani	Sails (IOI07_sails)	C++14	100 / 100	57 ms	3968 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

typedef long long llo;
llo n;
vector<pair<llo,llo>> tt;
llo tree[100001];
void u(llo i,llo j){
	while(i<100001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo ss(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
llo find(llo xx){
	llo cur=0;
	llo su=0;
	for(llo j=19;j>=0;j--){
		if(cur+(1<<j)>100000){
			continue;
		}
		if(tree[cur+(1<<j)]+su<xx){
			cur+=(1<<j);
			su+=tree[cur];
		}
	}
	return cur+1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		llo aa,bb;
		cin>>aa>>bb;
		tt.pb({aa,bb});
	}
	sort(tt.begin(),tt.end());
	for(auto j:tt){
		llo ind=100000-j.a+1;
		llo xx=ss(j.b+ind-1);
		llo ind2=find(xx);
		llo ind3=find(xx+1)-1;
		ind2=max(ind2,ind);
		u(ind,1);
		u(ind2,-1);
		llo yy=j.b-(ind2-ind);
		u(ind3-yy+1,1);
		u(ind3+1,-1);
	}
	llo ans=0;
	for(llo i=0;i<100001;i++){
		llo xx=ss(i);
		if(xx){
			ans+=((xx)*(xx-1))/2;
		}
	}
	cout<<ans<<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