Submission #120959

#	Time	Username	Problem	Language	Result	Execution time	Memory
120959		TadijaSebez	Fish (IOI08_fish)	C++11	100 / 100	1028 ms	26744 KiB

fish

#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 (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5