Submission #1186491

#TimeUsernameProblemLanguageResultExecution timeMemory
1186491harvsftwHorses (IOI15_horses)C++20
17 / 100
976 ms36968 KiB
#include <bits/stdc++.h> #include "horses.h" using namespace std; #define MOD (1'000'000'000 + 7) #define F(i, n) for(int i = 0; i < (n); i++) #define F_reverse(i, n) for(int i = (n - 1); i >= 0; i--) int N; int X[500000], Y[500000]; set<int> idx_with_2plus; struct segtree { int segtree[1 << 21]; int segtree_size = 1; const int zero = 0; void init(int n) { segtree_size = 1; while(segtree_size < n) { segtree_size <<= 1; } F(i, 2 * segtree_size) { segtree[i] = zero; } } int add(int a, int b) { return max(a, b); } int get(int i, int window_l, int window_r, int l, int r) { if(l <= window_l && window_r <= r) { return segtree[i]; } else if((window_l <= l && l <= window_r) || (window_l <= r && r <= window_r)) { int m = (window_l + window_r) / 2; return add(get(i * 2 + 0, window_l,m,l,r), get(i * 2 + 1,m + 1,window_r,l,r)); } else { return zero; } } int get(int l, int r) { if(l > r) { return zero; } return get(1, 0, segtree_size - 1, l, r); } void set(int i, int data) { i += segtree_size; segtree[i] = data; i /= 2; while(i > 0) { segtree[i] = add(segtree[i * 2 + 0], segtree[i * 2 + 1]); i /= 2; } } } ohio; int64_t mod_pow(int64_t a, int64_t b) { if(b == 0) { return 1; } else { int64_t m = mod_pow(a, b / 2); if(b & 1) { return m * m % MOD * a % MOD; } else { return m * m % MOD; } } } int64_t mod_inv(int64_t a) { return mod_pow(a, MOD - 2); } int64_t prod_all = 1; int solve() { __int128_t h = 1; bool overflow = false; int64_t ans = prod_all; int prv = N; for(auto it = idx_with_2plus.rbegin(); it != idx_with_2plus.rend(); --it) { int i = *it; ans = ans * mod_inv(X[i]) % MOD; int best_Y = ohio.get(i, prv - 1); if(best_Y > h) { // replace running product h = best_Y; } h *= X[i]; prv = i; if(h >= 1'000'000'000) { overflow = true; h %= MOD; break; } } if(!overflow) { // edge case: remaining X are 1s assert(ans == 1); int best_Y = ohio.get(0, prv - 1); if(best_Y > h) { h = best_Y; } } return ans * h % MOD; } int init(int _N, int _X[], int _Y[]) { N = _N; ohio.init(N); F(i, N) { X[i] = _X[i]; prod_all = prod_all * X[i] % MOD; if(X[i] > 1) { idx_with_2plus.insert(i); } Y[i] = _Y[i]; ohio.segtree[ohio.segtree_size + i] = Y[i]; } F_reverse(i, ohio.segtree_size) { ohio.segtree[i] = max(ohio.segtree[i * 2 + 0], ohio.segtree[i * 2 + 1]); } return solve(); } int updateX(int pos, int val) { if(X[pos] > 1 && val == 1) { idx_with_2plus.erase(pos); } else if(X[pos] == 1 && val > 1) { idx_with_2plus.insert(pos); } prod_all = prod_all * mod_inv(val) % MOD; X[pos] = val; prod_all = prod_all * val % MOD; return solve(); } int updateY(int pos, int val) { Y[pos] = val; ohio.set(pos, val); return solve(); }
#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...