oj.uz

Submission #500306

# Submission time Handle Problem Language Result Execution time Memory
500306 2021-12-30T16:48:34 Z MilosMilutinovic Sails (IOI07_sails) C++14
100 / 100
 581 ms 4748 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int M=2*N;
int n,h[N],k[N],ord[N];
int root,tsz,ls[M],rs[M],st[M];
void Set(int&c,int ss,int se,int qs,int qe,int x){
	if(!c)c=++tsz;
	if(ss>se||ss>qe||se<qs)return;
	if(qs<=ss&&se<=qe){st[c]+=x;return;}
	int mid=ss+se>>1;
	Set(ls[c],ss,mid,qs,qe,x);
	Set(rs[c],mid+1,se,qs,qe,x);
}
int Get(int c,int ss,int se,int qi){
	if(!c||ss>se||se<qi||ss>qi)return 0;
	if(ss==se)return st[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qi)+Get(rs[c],mid+1,se,qi)+st[c];
}
int FindL(int v,int mx){
	int l=1,r=mx,pos=mx;
	while(l<=r){
		int mid=l+r>>1;
		if(Get(root,1,N,mid)<=v)pos=mid,r=mid-1;
		else l=mid+1;
	}
	assert(pos!=-1);
	return pos;
}
int FindR(int v,int mx){
	int l=1,r=mx,pos=mx;
	while(l<=r){
		int mid=l+r>>1;
		if(Get(root,1,N,mid)>=v)pos=mid,l=mid+1;
		else r=mid-1;
	}
	assert(pos!=-1);
	return pos;
}
int main(){
	scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i %i",&h[i],&k[i]),ord[i]=i;
	sort(ord+1,ord+1+n,[&](int i,int j){return h[i]<h[j];});
	for(int i=1;i<=n;i++){
		int j=ord[i];
		int v=Get(root,1,N,h[j]-k[j]+1);
		int L=FindL(v,h[j]),R=FindR(v,h[j]);
		if(R==h[j]){
			Set(root,1,N,L,L+k[j]-1,1);
		}else{
			Set(root,1,N,R+1,h[j],1);
			k[j]-=(h[j]-R);
			Set(root,1,N,L,L+k[j]-1,1);
		}
	}
	long long ans=0;
	for(int i=1;i<=N;i++){
		long long c=Get(root,1,N,i);
		ans+=c*(c-1)/2;
	}
	printf("%lld",ans);
	return 0;
}

Compilation message

sails.cpp: In function 'void Set(int&, int, int, int, int, int)':
sails.cpp:11:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |  int mid=ss+se>>1;
      |          ~~^~~
sails.cpp: In function 'int Get(int, int, int, int)':
sails.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int mid=ss+se>>1;
      |          ~~^~~
sails.cpp: In function 'int FindL(int, int)':
sails.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=l+r>>1;
      |           ~^~
sails.cpp: In function 'int FindR(int, int)':
sails.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int mid=l+r>>1;
      |           ~^~
sails.cpp: In function 'int main()':
sails.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
sails.cpp:43:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  for(int i=1;i<=n;i++)scanf("%i %i",&h[i],&k[i]),ord[i]=i;
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 304 KB Output is correct
2 Correct 4 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 412 KB Output is correct
2 Correct 20 ms 568 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 908 KB Output is correct
2 Correct 130 ms 980 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1620 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 2496 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 3804 KB Output is correct
2 Correct 420 ms 3980 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 4460 KB Output is correct
2 Correct 300 ms 3936 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 4748 KB Output is correct
2 Correct 440 ms 3176 KB Output is correct