oj.uz

Submission #292825

# Submission time Handle Problem Language Result Execution time Memory
292825 2020-09-07T13:52:46 Z kshitij_sodani Sails (IOI07_sails) C++14
100 / 100
 57 ms 3968 KB 
#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.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 14 ms 1280 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1532 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2168 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3576 KB Output is correct
2 Correct 49 ms 3448 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3692 KB Output is correct
2 Correct 47 ms 3308 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3968 KB Output is correct
2 Correct 46 ms 3448 KB Output is correct