Submission #118348

#	Time	Username	Problem	Language	Result	Execution time	Memory
118348		baluteshih	Fish (IOI08_fish)	C++14	100 / 100	1132 ms	52472 KiB

fish

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
ll MOD,k;
pll fish[500005],mx[500005];
ll cnt[500005],seg[2][1500005],pl[500005],bound[500005];
 
void build(ll l,ll r,ll rt)
{
	if(l==r)
		return seg[0][rt]=cnt[l]+1,void();
	ll m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[0][rt]=seg[0][rt<<1]*seg[0][rt<<1|1]%MOD;
}
 
void build2(ll l,ll r,ll rt)
{
	if(l==r)
		return seg[1][rt]=1,void();
	ll m=l+r>>1;
	build2(l,m,rt<<1),build2(m+1,r,rt<<1|1);
	seg[1][rt]=seg[1][rt<<1]*seg[1][rt<<1|1]%MOD;
}
 
void modify(ll x,ll l,ll r,ll rt,ll v,ll t)
{
	if(l==r)
		return seg[t][rt]=v,void();
	ll m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1,v,t);
	else modify(x,m+1,r,rt<<1|1,v,t);
	seg[t][rt]=seg[t][rt<<1]*seg[t][rt<<1|1]%MOD;
}

ll query(ll L,ll R,ll l,ll r,ll rt)
{
	if(L<=l && R>=r) return seg[1][rt];
	ll m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1);
	if(L>m) return query(L,R,m+1,r,rt<<1|1);
	return query(L,R,l,m,rt<<1)*query(L,R,m+1,r,rt<<1|1)%MOD;
}

ll Query(ll l,ll r)
{
	if(l<=r) return query(l,r,1,k,1);
	return 1;
}
 
int main()
{jizz
	ll n,ans=0,nw;
	cin >> n >> k >> MOD,nw=n-1;
	for(int i=0;i<n;++i)
		cin >> fish[i].F >> fish[i].S,mx[fish[i].S].F=max(mx[fish[i].S].F,fish[i].F);
	for(int i=1;i<=k;++i)
		mx[i].S=i;
	sort(mx+1,mx+k+1);
	for(int i=1;i<=k;++i)
		pl[mx[i].S]=i;
	for(int i=0;i<n;++i)
		fish[i].S=pl[fish[i].S],++cnt[fish[i].S];
	sort(fish,fish+n),build(1,k,1),build2(1,k,1),MEM(bound,-1);
	for(int i=0;i<n;++i)
		if(!~bound[fish[i].S]&&fish[i].F*2>mx[fish[i].S].F)
			bound[fish[i].S]=fish[i].F;
	for(int i=k;i>0;--i)
	{
		while(nw>=0&&fish[nw].F*2>mx[i].F)
			modify(fish[nw].S,1,k,1,cnt[fish[nw].S],fish[nw].S>i),--cnt[fish[nw].S],--nw;
		modify(i,1,k,1,1,0);
		ans=(ans+seg[0][1]*cnt[i])%MOD;
		ans=(ans+seg[0][1]*Query(1,lower_bound(mx+1,mx+k+1,MP(bound[i]*2,0LL))-mx-1))%MOD;
		modify(i,1,k,1,cnt[i]+1,1);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

fish.cpp: In function 'void build(ll, ll, ll)':
fish.cpp:24:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
fish.cpp: In function 'void build2(ll, ll, ll)':
fish.cpp:33:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
fish.cpp: In function 'void modify(ll, ll, ll, ll, ll, ll)':
fish.cpp:42:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
fish.cpp: In function 'll query(ll, ll, ll, ll, ll)':
fish.cpp:51:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~

• 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