Submission #118424

#TimeUsernameProblemLanguageResultExecution timeMemory
118424briansuFish (IOI08_fish)C++14
88 / 100
598 ms41596 KiB
#include<bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll,ll> ii; #define REP1(i,n) for(ll i=1;i<=n;i++) #define FILL(i,n) memset(i,n,sizeof i) #define X first #define Y second #define pb push_back const ll MAXn=5e5+5; ll M; namespace seg{ int N; ll d[2 * MAXn]; void init(int n, ll *di){ N = n + 1; for(int i = 1;i <= n;i ++)d[N + i] = di[i] + 1; for(int i = N - 1;i > 0;i--)d[i] = d[i<<1] * d[i<<1|1] % M; } void ins(ll x, ll k){ for(d[x += N] = k;x > 1;x >>= 1)d[x>>1] = d[x] * d[x^1] % M; } ll qr(int l, int r){ ll ret = 1; for(l += N, r += N;l < r;l>>=1, r>>=1){ if(l&1)ret = ret * d[l++] % M; if(r&1)ret = ret * d[--r] % M; } return ret; } }; ii d[MAXn]; ll u[MAXn], ct[MAXn], mxsz[MAXn]; vector<ll> v[MAXn]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); ll n, m; cin>>n>>m>>M; REP1(i,n)cin>>d[i].X>>d[i].Y; sort(d + 1, d + 1 + n, greater<ii>()); ll nit = m; REP1(i, n){ if(u[d[i].Y])d[i].Y = u[d[i].Y]; else d[i].Y = u[d[i].Y] = nit--, mxsz[d[i].Y] = d[i].X; } for(int i = n;i > 0;i --)v[d[i].Y].pb(i), ct[d[i].Y] ++; seg::init(m, ct); ll tt = 0, it = 1; FILL(u, 0); REP1(i, n)if(!u[d[i].Y]){ u[d[i].Y] = 1; while(it <= n && d[it].X * 2 > d[i].X){ ct[d[it].Y]--; seg::ins(d[it].Y, ct[d[it].Y] + 1); it ++; } if(ct[d[i].Y] > 0)tt = (tt + ct[d[i].Y] * seg::qr(1, d[i].Y)) % M; ll t = lower_bound(mxsz + 1, mxsz + 1 + m, d[v[d[i].Y][ct[d[i].Y]]].X * 2) - mxsz; tt = (tt + seg::qr(d[i].Y + 1, t) * seg::qr(1, d[i].Y)) % M; } cout<<tt<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...