oj.uz

Submission #118339

# Submission time Handle Problem Language Result Execution time Memory
118339 2019-06-18T16:52:48 Z baluteshih Fish (IOI08_fish) C++14
33 / 100
 921 ms 26360 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];
bitset<500005> vis;
deque<ll> dq;
vector<ll> vec;
ll cnt[500005],seg[2][1500005],mx[500005],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()
{
	ll n,ans=0,nw;
	cin >> n >> k >> MOD,nw=n-1,vec.pb(-1);
	for(int i=0;i<n;++i)
		cin >> fish[i].F >> fish[i].S,mx[fish[i].S]=max(mx[fish[i].S],fish[i].F);
	for(int i=1;i<=k;++i)
		vec.pb(mx[i]);
	sort(ALL(vec));
	for(int i=1;i<=k;++i)
		pl[i]=lower_bound(ALL(vec),mx[i])-vec.begin();
	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>vec[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)
				modify(fish[nw].S,1,k,1,cnt[fish[nw].S],vis[fish[nw].S]),--cnt[fish[nw].S],--nw;
			modify(fish[i].S,1,k,1,1,0);
			ans=(ans+seg[0][1]*cnt[fish[i].S])%MOD;
			ans=(ans+seg[0][1]*Query(1,lower_bound(ALL(vec),bound[fish[i].S]*2)-vec.begin()-1))%MOD;
			vis[fish[i].S]=1,modify(fish[i].S,1,k,1,cnt[fish[i].S]+1,1);
		}
	cout << ans << "\n";
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is 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 4224 KB Output is correct
2 Incorrect 6 ms 4352 KB Output isn't correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 372 ms 12148 KB Output is 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 8 ms 4352 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 7416 KB Output is correct
2 Incorrect 262 ms 10348 KB Output isn't correct

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 9208 KB Output is correct
2 Incorrect 457 ms 13412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

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

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 9328 KB Output is correct
2 Correct 460 ms 12632 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 12368 KB Output is correct

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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