Submission #118421

#TimeUsernameProblemLanguageResultExecution timeMemory
118421briansuFish (IOI08_fish)C++14
100 / 100
1022 ms58736 KiB
//{ #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double lf; typedef pair<ll,ll> ii; #define REP(i,n) for(ll i=0;i<n;i++) #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 SZ(_a) (int)_a.size() #define ALL(_a) _a.begin(),_a.end() #define pb push_back #ifdef brian #define debug(...) do{\ fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\ _do(__VA_ARGS__);\ }while(0) template<typename T>void _do(T &&_x){cerr<<_x<<endl;} template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);} template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";} template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb) { _s<<"{"; for(It _it=_ita;_it!=_itb;_it++) { _s<<(_it==_ita?"":",")<<*_it; } _s<<"}"; return _s; } template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));} template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));} template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));} template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;} #define IOS() #else #define debug(...) #define pary(...) #define endl '\n' #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #endif // brian //} const ll MAXn=5e5+5,MAXlg=__lg(MAXn)+2; const ll INF=ll(1e15); ll M; namespace seg{ int N; ll d[2 * MAXn]; void init(int n, ll *di) { N = n + 1; d[N] = 0; 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(); ll n, m; cin>>n>>m; cin>>M; REP1(i,n)cin>>d[i].X>>d[i].Y; sort(d + 1, d + 1 + n, greater<ii>()); pary(d + 1, d + 1 + n); // relabel { 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] ++; pary(d + 1, d + 1 + n); seg::init(m, ct); FILL(u, 0); ll tt = 0, it = 1; 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; debug(d[i].Y, tt); 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; debug(d[i].Y, tt, t); } 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...