제출 #837873

#제출 시각아이디문제언어결과실행 시간메모리
837873caganyanmazFish (IOI08_fish)C++17
0 / 100
802 ms65536 KiB
#include <bits/stdc++.h> #define pb push_back #define mp(x...) array<int, 2>({x}) using namespace std; #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif constexpr static int MXN = 5e5; constexpr static int MXST = MXN<<1; int MOD, n, k; int add() { return 0; } int mul() { return 1; } template<typename... V> int add(int a, V... v) { return (a+add(v...)) % MOD; } template<typename... V> int mul(int64_t a, V... v) { return (a*mul(v...)) % MOD; } int st[MXST]; int bound[MXN]; array<int, 2> v[MXN]; void update(int i, int val) { for (st[i+=k]+=val;i>1;i>>=1) st[i>>1] = mul(st[i], st[i^1]); } int query(int l, int r) { int res = 1; for (l+=k,r+=k;l<r;l>>=1,r>>=1) { if (l&1) res = mul(res, st[l++]); if (r&1) res = mul(res, st[--r]); } return res; } array<int, 2> last[MXN]; set<int> pos[MXN]; int p[MXN]; void manage_types() { vector<int> a; for (int i = 0; i < n; i++) a.pb(v[i][1]); sort(a.begin(), a.end()); auto it = unique(a.begin(), a.end()); a.erase(it, a.end()); for (int i = 0; i < n; i++) v[i][1] = lower_bound(a.begin(), a.end(), v[i][1]) - a.begin(); for (int i = 0; i < n; i++) last[v[i][1]] = {i, v[i][1]}; sort(last, last + k); for (int i = 0; i < k; i++) p[last[i][1]] = k-i-1; for (int i = 0; i < n; i++) v[i][1] = p[v[i][1]]; } void manage_pos() { for (int i = 0; i < n; i++) pos[v[i][1]].insert(i); } set<array<int, 2>> ee; int main() { cin >> n; cin >> k; cin >> MOD; for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1]; sort(v, v + n); fill(st, st + 2*k, 1); manage_types(); manage_pos(); for (int i = 0; i < n; i++) debug(v[i]); int r; for (r = 0; v[r][0]*2 <= v[n-1][0]; r++) update(v[r][1], 1); int sum = query(0, k); debug(sum); ee.insert({n-1, 0}); int j = 1; for (int i = n-2; i >= 0; i--) { debug(v[i][1], j); if (v[i][1] != j) continue; while (v[r-1][0]*2>v[i][0]) { debug(r-1); update(v[--r][1], -1); } int last_point = *pos[v[i][1]].upper_bound(v[i][0] / 2); auto it = ee.upper_bound(mp(last_point, -1)); int ls = (*it)[1]; if ((*it)[0] == last_point) ls--; int all_zero = query(j, k); debug(ls+1, j, j+1, k); int some_zero = mul(query(ls+1, j), query(j+1, k)); int inter = query(j+1, k); debug(v[i][0], j, all_zero, some_zero, inter); sum = add(sum, all_zero, some_zero, -inter); ee.insert(mp(i, v[i][1]));// Current point j++; } cout << sum << "\n"; }
#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...