Submission #1192278

#TimeUsernameProblemLanguageResultExecution timeMemory
1192278ohdarndjeHorses (IOI15_horses)C++20
34 / 100
1596 ms35864 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second const int mod = 1e9 + 7; struct ST1{ vector<int> a; int n; void init(int ns){ n = ns; a.resize(n + 1); } void upd(int p, int x){ a[p] = x; } int get(int l, int r){ int out = 0; for (int i = l; i <= r; i++){ out = max(out, a[i]); } return out; } }; struct ST2{ vector<int> a; int n; void init(int ns){ n = ns; a.resize(n + 1); } void upd(int p, int x){ a[p] = x; } int get(int l, int r){ if (!r) return 1; int out = 1; for (int i = l; i <= r; i++){ out = (1LL * out * a[i]) % mod; } return out; } }; ST1 T; ST2 F; set<int> st; vector<int> x, y; int n; int get(){ if (st.empty()) return T.get(1, n); auto it = prev(st.end()); ll P = 1; vector<int> f; while (true){ P *= x[*it]; f.pb(*it); if (P > 1e9) break; if (it == st.begin()){ break; } it--; } reverse(f.begin(), f.end()); f.pb(n + 1); if (P <= 1e9 && f[0] != 1) f.insert(f.begin(), 1); ll out = T.get(f[0], f[1] - 1); P = 1; for (int i = 1; i + 1 < f.size(); i++){ int l = f[i], r = f[i + 1] - 1; P *= x[l]; out = max(out, P * T.get(l, r)); } out %= mod; out = (out * x[f[0]]) % mod; return (1LL * F.get(1, f[0] - 1) * out) % mod; } int init(int N, int X[], int Y[]){ n = N; x.resize(n + 1); y.resize(n + 1); T.init(n); F.init(n); for (int i = 1; i <= n; i++){ x[i] = X[i - 1]; y[i] = Y[i - 1]; if (x[i] > 1){ st.insert(i); } T.upd(i, y[i]); F.upd(i, x[i]); } return get(); } int updateX(int p, int v){ p++; if (x[p] > 1) st.erase(p); x[p] = v; if (v > 1) st.insert(p); F.upd(p, v); return get(); } int updateY(int p, int v){ p++; y[p] = v; T.upd(p, v); return get(); }
#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...