제출 #118326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118326		baluteshih	Fish (IOI08_fish)	C++14	17 / 100	941 ms	24172 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;
pll fish[500005];
bitset<500005> vis;
deque<ll> dq;
ll cnt[500005],seg[2][1500005],mx[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;
}
 
int main()
{jizz
	ll n,k,ans=0,nw;
	cin >> n >> k >> MOD,nw=n-1;
	for(int i=0;i<n;++i)
		cin >> fish[i].F >> fish[i].S,++cnt[fish[i].S],mx[fish[i].S]=max(mx[fish[i].S],fish[i].F);
	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])
			bound[fish[i].S]=fish[i].F;
	for(int i=n-1;i>=0;--i)
		if(!vis[fish[i].S])
		{
			while(nw>=0&&fish[nw].F*2>fish[i].F)
				if(!vis[fish[nw].S]) 
					modify(fish[nw].S,1,k,1,cnt[fish[nw].S],0),--cnt[fish[nw].S],--nw;
				else if(fish[i].F*2>mx[fish[nw].S])
					modify(fish[nw].S,1,k,1,cnt[fish[nw].S],1),--cnt[fish[nw].S],--nw;
				else
					--cnt[fish[nw].S],--nw;
			modify(fish[i].S,1,k,1,1,0);
			ans=(ans+seg[0][1]*cnt[fish[i].S])%MOD;
			while(dq.size()&&bound[fish[i].S]*2<=mx[dq[0]])
				modify(dq[0],1,k,1,1,1),dq.pop_front();
			ans=(ans+seg[0][1]*seg[1][1])%MOD;
			vis[fish[i].S]=1,modify(fish[i].S,1,k,1,cnt[fish[i].S]+1,1),dq.pb(fish[i].S);
		}
	cout << ans << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'void build(ll, ll, ll)':
fish.cpp:26:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
fish.cpp: In function 'void build2(ll, ll, ll)':
fish.cpp:35: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:44:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5