oj.uz

Submission #120959

# Submission time Handle Problem Language Result Execution time Memory
120959 2019-06-25T20:08:41 Z TadijaSebez Fish (IOI08_fish) C++11
100 / 100
 1028 ms 26744 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int mod;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int sub(int x, int y){ x-=y;return x<0?x+mod:x;}
const int N=500050;
const int M=2*N;
struct SegmentTree
{
	int sum[M];
	SegmentTree(){ for(int i=1;i<M;i++) sum[i]=1;}
	void Set(int i, int f){ for(sum[i+=N]+=f;i>1;i>>=1) sum[i>>1]=mul(sum[i],sum[i^1]);}
	int Get(int l, int r)
	{
		int ans=1;
		for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ans=mul(ans,sum[l++]);
			if(r%2==0) ans=mul(ans,sum[r--]);
		}
		return ans;
	}
} ST;
int col[N],sz[N],id[N],now[N],fir[N],sec[N],po[N];
bool best[N],was[N];
int main()
{
	int n,k;
	scanf("%i %i %i",&n,&k,&mod);
	for(int i=1;i<=n;i++) scanf("%i %i",&sz[i],&col[i]),id[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return sz[i]<sz[j];});
	for(int i=1;i<=n;i++) po[id[i]]=i;
	for(int i=1;i<=n;i++)
	{
		swap(sz[i],sz[id[i]]);
		swap(col[i],col[id[i]]);
		swap(id[i],id[po[i]]);
		swap(po[id[i]],po[id[po[i]]]);
	}
	int cnt=0;
	for(int i=n;i>=1;i--)
	{
		if(!now[col[i]]) now[col[i]]=++cnt,best[i]=1,fir[cnt]=i;
		col[i]=now[col[i]];
		if(sz[i]*2>sz[fir[col[i]]]) sec[col[i]]=i;
	}
	int ans=0;
	for(int i=1,j=1;i<=n;i++)
	{
		while(sz[j]*2<=sz[i]) ST.Set(col[j++],1);
		if(!best[i]) continue;
		ST.Set(col[i],-1);
		ans=add(ans,ST.Get(col[i],cnt));
		int top=cnt,bot=1,mid,tmp=0;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(sz[fir[mid]]>=sz[sec[col[i]]]*2) tmp=mid,bot=mid+1;
			else top=mid-1;
		}
		ans=add(ans,mul(ST.Get(tmp+1,col[i]-1),ST.Get(col[i]+1,cnt)));
		ST.Set(col[i],1);
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:59:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
fish.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&mod);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:32:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&sz[i],&col[i]),id[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4324 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 274 ms 18112 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10036 KB Output is correct
2 Correct 151 ms 11424 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Output is correct
2 Correct 9 ms 4480 KB Output is correct
3 Correct 9 ms 4352 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 13176 KB Output is correct
2 Correct 317 ms 18992 KB Output is correct
3 Correct 285 ms 18972 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 18252 KB Output is correct
2 Correct 278 ms 19184 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 13680 KB Output is correct
2 Correct 299 ms 19292 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 18084 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 20000 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 17392 KB Output is correct
2 Correct 403 ms 21656 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 20652 KB Output is correct
2 Correct 449 ms 15868 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 18680 KB Output is correct
2 Correct 503 ms 21584 KB Output is correct
3 Correct 669 ms 21624 KB Output is correct
4 Correct 514 ms 21428 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 22904 KB Output is correct
2 Correct 1018 ms 25820 KB Output is correct
3 Correct 961 ms 26744 KB Output is correct
4 Correct 1028 ms 25480 KB Output is correct