oj.uz

Submission #118326

# Submission time Handle Problem Language Result Execution time Memory
118326 2019-06-18T16:18:41 Z baluteshih Fish (IOI08_fish) C++14
17 / 100
 941 ms 24172 KB 
#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";
}

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4352 KB Output isn't correct

Subtask #4
4.0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4396 KB Output is correct
2 Incorrect 5 ms 4352 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct
2 Incorrect 162 ms 12192 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4352 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4352 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 7544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4480 KB Output is correct
2 Incorrect 8 ms 4480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 9144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 12484 KB Output is correct
2 Incorrect 212 ms 12508 KB Output isn't correct

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9336 KB Output is correct
2 Incorrect 231 ms 12560 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 12152 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 308 ms 13596 KB Output isn't correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 14028 KB Output is correct
2 Correct 648 ms 18748 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 785 ms 22300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 22216 KB Output is correct
2 Incorrect 670 ms 18040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 941 ms 24172 KB Output isn't correct
2 Halted 0 ms 0 KB -