oj.uz

Submission #118348

# Submission time Handle Problem Language Result Execution time Memory
118348 2019-06-18T17:05:20 Z baluteshih Fish (IOI08_fish) C++14
100 / 100
 1132 ms 52472 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,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

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

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 5 ms 4352 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct
2 Correct 165 ms 12500 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 6 ms 4352 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 7800 KB Output is correct
2 Correct 101 ms 8676 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4480 KB Output is correct
2 Correct 10 ms 4480 KB Output is correct
3 Correct 21 ms 4480 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 9404 KB Output is correct
2 Correct 230 ms 12664 KB Output is correct
3 Correct 222 ms 13560 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 12652 KB Output is correct
2 Correct 212 ms 13192 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 9592 KB Output is correct
2 Correct 234 ms 13052 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 12612 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 14120 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 14500 KB Output is correct
2 Correct 527 ms 19832 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 24656 KB Output is correct
2 Correct 472 ms 26744 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 24732 KB Output is correct
2 Correct 580 ms 19832 KB Output is correct
3 Correct 593 ms 33320 KB Output is correct
4 Correct 615 ms 27056 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 27004 KB Output is correct
2 Correct 1132 ms 51500 KB Output is correct
3 Correct 981 ms 52472 KB Output is correct
4 Correct 1066 ms 49232 KB Output is correct