제출 #1277509

#제출 시각아이디문제언어결과실행 시간메모리
1277509k12_khoi말 (IOI15_horses)C++17
34 / 100
1598 ms55216 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,ll> #define X first #define Y second const int N = 500000 + 5; const int mod = 1000000007; const int limit = 1000000000; int n, request, type, x, y, u, v, k; int a[N], b[N], Xarr[N], Yarr[N], t[4 * N], lazy[4 * N], tTwo[4 * N]; set<int> se; set<int>::iterator it; int mul(int x, int y) { return int((1LL * x * y) % mod); } int luythua(int x, int nexp) { int c = 1; while (nexp) { if (nexp & 1) c = mul(c, x); x = mul(x, x); nexp >>= 1; } return c; } void down(int id) { if (lazy[id] != 1) { lazy[id << 1] = mul(lazy[id << 1], lazy[id]); lazy[id << 1 | 1] = mul(lazy[id << 1 | 1], lazy[id]); tTwo[id << 1] = mul(tTwo[id << 1], lazy[id]); tTwo[id << 1 | 1] = mul(tTwo[id << 1 | 1], lazy[id]); lazy[id] = 1; } } // update_range uses globals u,v,k like original void update_range(int id, int l, int r) { if (u > r || v < l) return; if (u <= l && r <= v) { tTwo[id] = mul(tTwo[id], k); lazy[id] = mul(lazy[id], k); return; } down(id); int m = (l + r) >> 1; update_range(id << 1, l, m); update_range(id << 1 | 1, m + 1, r); } // update_point uses globals u,k: set t at leaf u to k void update_point(int id, int l, int r) { if (l == r) { t[id] = k; return; } int m = (l + r) >> 1; if (u <= m) update_point(id << 1, l, m); else update_point(id << 1 | 1, m + 1, r); t[id] = max(t[id << 1], t[id << 1 | 1]); } // get_range uses globals u,v int get_range(int id, int l, int r) { if (u > r || v < l) return 0; if (u <= l && r <= v) return t[id]; down(id); int m = (l + r) >> 1; return max(get_range(id << 1, l, m), get_range(id << 1 | 1, m + 1, r)); } // get_point uses global u int get_point(int id, int l, int r) { if (l == r) return tTwo[id]; down(id); int m = (l + r) >> 1; if (u <= m) return get_point(id << 1, l, m); else return get_point(id << 1 | 1, m + 1, r); } // build using pref_mod to avoid side effects of modifying cur inside recursion function<void(int,int,int)> build; // forward int init(int nn, int aarr[], int barr[]) { ::n = nn; for (int i = 0; i < n; ++i) { Xarr[i] = aarr[i]; Yarr[i] = barr[i]; } // prepare prefix modulo array (prefix_mod[i] = X[0]*...*X[i-1] mod) // init segment tree arrays (clean) int SZ = 4 * (n + 5); for (int i = 0; i < SZ; ++i) { t[i] = 0; lazy[i] = 1; tTwo[i] = 1; } long long cur = 1; // build function (uses prefix_mod) build = [&](int id, int l, int r) { lazy[id] = 1; tTwo[id] = 1; if (l == r) { if (l == 0) t[id] = 1; else t[id] = Yarr[l - 1],cur=mul(cur,Xarr[l-1]); tTwo[id] = cur; // prefix mod for leaf l return; } int m = (l + r) >> 1; build(id << 1, l, m); build(id << 1 | 1, m + 1, r); t[id] = max(t[id << 1], t[id << 1 | 1]); }; // build tree build(1, 0, n); // fill set se se.clear(); se.insert(0); for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1); // find best: iterate as you requested: multiply cur by X[old-1] then --it then check pos=*it it = prev(se.end()); int best = *it; // ma: pair(maxY, den) where den is cur-ref per your semantics; init with last element u = *it; v = n; pii ma = make_pair(get_range(1, 0, n), 1); cur=1; while (it != se.begin()) { int old = *it; if (old) { cur = cur * 1LL * Xarr[old - 1]; if (cur >= limit) cur = limit; // cap to avoid overflow } --it; int pos = *it; u = pos; v = n; int temp = get_range(1, 0, n); // compare ratios: ma.first/ma.second < temp/cur if ((long long)ma.first * cur < (long long)temp * ma.second) { best = pos; ma.first = temp; ma.second = 1; // follow your desired reset behavior cur = 1; } } u = best; int prefMod = get_point(1, 0, n); u = best; v = n; int ans = mul(prefMod, get_range(1, 0, n)); return ans; } int updateX(int pos0, int val) { int pos = pos0 + 1; if (Xarr[pos - 1] != val) { if (Xarr[pos - 1] == 1) se.insert(pos); k = mul(luythua(Xarr[pos - 1], mod - 2), val); // multiplier modulo u = pos; v = n; update_range(1, 0, n); Xarr[pos - 1] = val; if (val == 1) se.erase(pos); } // find best again with same iteration logic it = prev(se.end()); int best = *it; u = *it; v = n; pii ma = make_pair(get_range(1, 0, n), 1); long long cur = 1; while (it != se.begin()) { int old = *it; if (old) { cur = cur * 1LL * Xarr[old - 1]; if (cur >= limit) cur = limit; } --it; int pos2 = *it; u = pos2; v = n; int temp = get_range(1, 0, n); if ((long long)ma.first * cur < (long long)temp * ma.second) { best = pos2; ma.first = temp; ma.second = 1; cur = 1; } } u = best; int prefMod = get_point(1, 0, n); u = best; v = n; return mul(prefMod, get_range(1, 0, n)); } int updateY(int pos0, int val) { int pos = pos0 + 1; if (Yarr[pos - 1] != val) { u = pos; k = val; update_point(1, 0, n); // set t at leaf pos to val Yarr[pos - 1] = val; } // find best again it = prev(se.end()); int best = *it; u = *it; v = n; pii ma = make_pair(get_range(1, 0, n), 1); long long cur = 1; while (it != se.begin()) { int old = *it; if (old) { cur = cur * 1LL * Xarr[old - 1]; if (cur >= limit) cur = limit; } --it; int pos2 = *it; u = pos2; v = n; int temp = get_range(1, 0, n); if ((long long)ma.first * cur < (long long)temp * ma.second) { best = pos2; ma.first = temp; ma.second = 1; cur = 1; } } u = best; int prefMod = get_point(1, 0, n); u = best; v = n; return mul(prefMod, get_range(1, 0, 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...