Submission #1012130

#TimeUsernameProblemLanguageResultExecution timeMemory
1012130vjudge1Fish (IOI08_fish)C++17
70 / 100
1643 ms65536 KiB
#include <bits/stdc++.h> #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define ll long long #define mp make_pair #define pb push_back #define F first #define S second #define pii pair < int, int > using namespace std; const int N = 5e5+10, K = 5e5+10; const int logN = 20, maxN = (1<<20), startpos = maxN-1; int n, k, m; pii ribe[N]; int najvecidrag[K]; int draginterval[K]; int cur; int lowout[K]; int st[maxN<<1]; vector < int > dragulji; int sol; bool rip[K]; bool ripp[7010][7010]; int temp[7010]; bool dragsort1( int a, int b ) { if(najvecidrag[a] > najvecidrag[b]) return 1; return 0; } bool dragsort2( int a, int b ) { if(lowout[a] > lowout[b]) return 1; return 0; } int add( int a, int b ) { return (a + b >= m) ? a+b-m : a+b; } int mul( int a, int b ) { return (ll) a * b % m; } inline void merge( int i ) { st[i] = mul(st[i*2+1], st[i*2+2]); return; } inline void update( int i, int v ) { i += startpos; st[i] += v; while(i != 0) { i = (i - 1) / 2; merge(i); } return; } int main( void ) { FIO cin >> n >> k >> m; for(int i = 0; i < n; i++) { cin >> ribe[i].F >> ribe[i].S; ribe[i].S--; } sort(ribe, ribe + n); cur = 0; for(int i = 0; i < n; i++) { najvecidrag[ribe[i].S] = i; while(ribe[cur].F * 2 <= ribe[i].F) { cur++; } draginterval[ribe[i].S] = cur; lowout[ribe[i].S] = n; } for(int i = 0; i < n; i++) { if(i >= draginterval[ribe[i].S]) { lowout[ribe[i].S] = min(lowout[ribe[i].S], i); } } for(int i = 0; i < maxN<<1; i++) st[i] = 1; for(int i = 0; i < n; i++) { update(ribe[i].S, 1); } for(int i = 0; i < k; i++) { dragulji.pb(i); } sort(dragulji.begin(), dragulji.end(), dragsort1); cur = n-1; for(int i = 0; i < k; i++) { while(cur >= 0 && draginterval[dragulji[i]] <= cur) { if(!rip[ribe[cur].S])update(ribe[cur].S, -1); cur--; } // cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n"; update(dragulji[i], -1); sol = add(sol, st[0]); update(dragulji[i], 1-st[dragulji[i] + startpos]); rip[dragulji[i]] = 1; // cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << " " << st[startpos+3] << "\n\n"; } for(int i = 0; i < k; i++) rip[i] = 0; // cout << sol << "\n"; cur = n-1; for(int i = 0; i < maxN<<1; i++) st[i] = 1; for(int i = 0; i < n; i++) { update(ribe[i].S, 1); } for(int i = 0; i < k; i++) { for(int j = 0; j < k; j++) { if(draginterval[i] > lowout[j]) { ripp[j][i] = 1; } if(i==j) ripp[j][i] = 1; } } // cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n\n\n"; for(int i = 0; i < k; i++) { while(cur >= 0 && draginterval[dragulji[i]] <= cur) { update(ribe[cur].S, -1); cur--; } // cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n"; for(int j = 0; j < k; j++) { if(ripp[dragulji[i]][j]) { temp[j] = st[j + startpos] - 1; update(j, - temp[j]); } } sol = add(sol, st[0]); // cout << st[startpos+0] << " " << st[startpos+1] << " " << st[startpos+2] << "\n\n"; for(int j = 0; j < k; j++) { if(ripp[dragulji[i]][j]) { update(j, temp[j]); } } } cout << sol; return 0; }
#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...