Submission #428489

#TimeUsernameProblemLanguageResultExecution timeMemory
428489arayiFish (IOI08_fish)C++17
9 / 100
796 ms29036 KiB
//Arayi #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <queue> #include <stack> #include <algorithm> #include <math.h> #include <vector> #include <cstring> #include <ctime> #include <set> #include <bitset> #include <map> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <ctime> #include <climits> #include <cassert> #include <chrono> #include <random> #include <complex> #define fr first #define sc second #define MP make_pair #define ad push_back #define PB push_back #define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define lli long long int #define y1 arayikhalatyan #define j1 jigglypuff #define ld long double #define itn int #define pir pair<int, int> #define all(x) (x).begin(), (x).end() #define str string #define enl endl #define en endl #define cd complex<long double> #define vcd vector<cd> #define vii vector<int> #define vlli vector<lli> using namespace std; lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); } ld dist(ld x, ld y1, ld x2, ld y2) { return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2)); } lli S(lli a) { return (a * (a + 1LL)) / 2; } mt19937 rnd(363542); char vow[] = { 'a', 'e', 'i', 'o', 'u' }; int dx[] = { 0, -1, 0, 1, -1, -1, 1, 1, 0 }; int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1, 0 }; const int N = 1e6 + 30; lli mod = 1e9 + 7; const ld pi = acos(-1); const int T = 200; lli bp(lli a, lli b = mod - 2LL) { lli ret = 1; while (b) { if (b & 1) ret *= a, ret %= mod; a *= a; a %= mod; b >>= 1; } return ret; } ostream& operator<<(ostream& c, pir a) { c << a.fr << " " << a.sc; return c; } template<class T> void maxi(T& a, T b) { a = max(a, b); } template <class T> void mini(T& a, T b) { a = min(a, b); } int n, k; pair<int, lli> a[N]; lli qan[N], col[N], cl[N], ans; lli t[4*N], t1[4*N]; void upd1(int q, lli v, int l = 1, int r = k, int nd = 1) { if(q > r || q < l) return; if(l == r) { t1[nd] = v; return; } int mid = (l + r) / 2; upd1(q, v, l, mid, nd*2); upd1(q, v, mid + 1, r, nd * 2 + 1); t1[nd] = (t1[nd*2] * t1[nd*2+1]) % mod; } void upd(int q, lli v, int l = 1, int r = k, int nd = 1) { if(q > r || q < l) return; if(l == r) { t[nd] = v; return; } int mid = (l + r) / 2; upd(q, v, l, mid, nd*2); upd(q, v, mid + 1, r, nd * 2 + 1); t[nd] = (t[nd*2] * t[nd*2+1]) % mod; } lli qry1(int l, int r, int nl = 1, int nr = k, int nd = 1) { if(l > nr || r < nl) return 1; if(l == nl && r == nr) return t1[nd]; int mid = (nl + nr) / 2; return (qry1(l, min(mid, r), nl, mid, nd*2) * qry1(max(mid + 1, l), r, mid + 1, nr, nd*2 + 1)) % mod; } lli qry(int l, int r, int nl = 1, int nr = k, int nd = 1) { if(l > nr || r < nl) return 1; if(l == nl && r == nr) return t[nd]; int mid = (nl + nr) / 2; return (qry(l, min(mid, r), nl, mid, nd*2) * qry(max(mid + 1, l), r, mid + 1, nr, nd*2 + 1)) % mod; } int main() { fastio; //freopen("input.in", "r", stdin); cin >> n >> k >> mod; for (int i = 0; i < n; i++) cin >> a[i].fr >> a[i].sc; sort(a,a+n); int i1 = -1; for (int i = 0; i < n; i++) if(a[i].fr*2 <= a[n-1].fr) qan[a[i].sc]++, i1 = i; for (int i = 1; i <= k; i++) upd(i, qan[i] + 1), upd1(i, qan[i] + 1), col[i] = qan[i]; //cout << t[1] << endl; for (int i = n - 1; i >= 0; i--) { if(i == n - 1) { ans += t[1]; col[a[i].sc]++; cl[a[i].sc] = 1; upd1(a[i].sc, 1); continue; } while(i1 >= 0 && a[i1].fr*2 > a[i].fr) { qan[a[i1].sc]--; upd(a[i1].sc, qan[a[i1].sc] + 1); if(!cl[a[i1].sc]) upd1(a[i1].sc, qan[a[i1].sc] + 1); i1--; } if(cl[a[i].sc]) continue; if(col[a[i].sc] == qan[a[i].sc]) { col[a[i].sc]++; upd(a[i].sc, 1); ans += t[1], ans %= mod; upd(a[i].sc, qan[a[i].sc] + 1); upd1(a[i].sc, 1); ans -= t1[1], ans = (ans + mod) % mod; upd1(a[i].sc, qan[a[i].sc] + 1); } ans += t1[1], ans %= mod; upd1(a[i].sc, 1); cl[a[i].sc] = 1; } cout << ans << endl; 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...