Submission #1277522

#TimeUsernameProblemLanguageResultExecution timeMemory
1277522k12_khoiHorses (IOI15_horses)C++17
100 / 100
664 ms46004 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 1LL*x*y%mod; } int luythua(int x,int n) { int c=1; while (n) { if (n&1) c=mul(c,x); x=mul(x,x); n/=2; } return c; } void down(int id) { if (lazy[id]!=1) { lazy[id*2]=mul(lazy[id*2],lazy[id]); lazy[id*2+1]=mul(lazy[id*2+1],lazy[id]); tTwo[id*2]=mul(tTwo[id*2],lazy[id]); tTwo[id*2+1]=mul(tTwo[id*2+1],lazy[id]); lazy[id]=1; } } void update_range(int id,int l,int r) { if (u>r or v<l) return; if (u<=l and v>=r) { tTwo[id]=mul(tTwo[id],k); lazy[id]=mul(lazy[id],k); return; } down(id); int m=(l+r)/2; update_range(id*2,l,m); update_range(id*2+1,m+1,r); } void update_point(int id,int l,int r) { if (l==r) { t[id]=k; return; } int m=(l+r)/2; if (u<=m) update_point(id*2,l,m); else update_point(id*2+1,m+1,r); t[id]=max(t[id*2],t[id*2+1]); } int get_range(int id,int l,int r) { if (u>r or v<l) return 0; if (u<=l and v>=r) return t[id]; int m=(l+r)/2; return max(get_range(id*2,l,m),get_range(id*2+1,m+1,r)); } ll get_point(int id,int l,int r) { if (l==r) return tTwo[id]; down(id); int m=(l+r)/2; if (u<=m) return get_point(id*2,l,m); else return get_point(id*2+1,m+1,r); } // build using pref_mod to avoid side effects of modifying cur inside recursion function<void(int,int,int, const vector<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) vector<int> prefix_mod(n + 1); prefix_mod[0] = 1; for (int i = 1; i <= n; ++i) prefix_mod[i] = mul(prefix_mod[i - 1], Xarr[i - 1]); long long cur=1; // build function (uses prefix_mod) build = [&](int id, int l, int r, const vector<int> &pref_mod) { 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, pref_mod); build(id << 1 | 1, m + 1, r, pref_mod); t[id] = max(t[id << 1], t[id << 1 | 1]); }; // build tree build(1, 0, n, prefix_mod); // fill set se se.insert(0); for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1); it=--se.end(); u=*it; v=n; pii ma=make_pair(get_range(1,0,n),1); ll temp; int best=*it; cur=1; while (it!=se.begin()) { if (*it) cur*=Xarr[(*it)-1]; if (cur>=limit) break; it--; u=*it; v=n; int temp=get_range(1,0,n); if (ma.X*cur<temp*ma.Y) { best=*it; cur=1; ma=make_pair(temp,cur); } } 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); } it=--se.end(); u=*it; v=n; pii ma=make_pair(get_range(1,0,n),1); ll temp; int best=*it; ll cur=1; while (it!=se.begin()) { if (*it) cur*=Xarr[(*it)-1]; if (cur>=limit) break; it--; u=*it; v=n; int temp=get_range(1,0,n); if (ma.X*cur<temp*ma.Y) { best=*it; cur=1; ma=make_pair(temp,cur); } } 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; } it=--se.end(); u=*it; v=n; pii ma=make_pair(get_range(1,0,n),1); ll temp; int best=*it; ll cur=1; while (it!=se.begin()) { if (*it) cur*=Xarr[(*it)-1]; if (cur>=limit) break; it--; u=*it; v=n; int temp=get_range(1,0,n); if (ma.X*cur<temp*ma.Y) { best=*it; cur=1; ma=make_pair(temp,cur); } } 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...