Submission #1138978

#TimeUsernameProblemLanguageResultExecution timeMemory
1138978Ekber_EkberHorses (IOI15_horses)C++20
17 / 100
1596 ms66888 KiB
#include "horses.h" #include <bits/stdc++.h> #define ll long long #define itn int #define endl "\n" #define ff first #define ss second #define pb push_back #define ppb pop_back #define ins insert #define lb lower_bound #define ub upper_bound #define bs binary_search #define count1 __builtin_popcount #define all(v) v.begin(), v.end() using namespace std; struct point{ ll ans, sum; double lg, anslg; }; constexpr ll MAX = 5e+5 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX); ll n; vector <ll> a, b; vector <point> t(4 * MAX); ll exp(ll a, ll b) { if (b == 0) return 1; if (b % 2) return (a * exp(a, b-1)) % MOD; return exp((a*a)%MOD, b/2); } void build(ll v, ll tl, ll tr) { if (tl == tr) { t[v].ans = (a[tl] * b[tl]) % MOD; t[v].sum = a[tl] % MOD; t[v].lg = log10(a[tl]); t[v].anslg = log10(t[v].ans); return; } ll tm = (tl + tr) / 2; build(v*2, tl, tm); build(v*2+1, tm+1, tr); t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD; if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) { t[v].ans = t[v*2].ans; t[v].anslg = t[v*2].anslg; } else { t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD; t[v].anslg = t[v*2].lg + t[v*2+1].anslg; } t[v].lg = t[v*2].lg + t[v*2+1].lg; } void updatex(ll v, ll tl, ll tr, ll i, ll x) { if (tl == tr) { t[v].ans = (x * b[tl]) % MOD; t[v].sum = x % MOD; a[tl] = x; return; } ll tm = (tl + tr) / 2; if (i <= tm) { updatex(v*2, tl, tm, i, x); } else { updatex(v*2+1, tm+1, tr, i, x); } t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD; if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) { t[v].ans = t[v*2].ans; t[v].anslg = t[v*2].anslg; } else { t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD; t[v].anslg = t[v*2].lg + t[v*2+1].anslg; } t[v].lg = t[v*2].lg + t[v*2+1].lg; } void updatey(ll v, ll tl, ll tr, ll i, ll y) { if (tl == tr) { t[v].ans = (a[tl] * y) % MOD; b[tl] = y; return; } ll tm = (tl + tr) / 2; if (i <= tm) { updatey(v*2, tl, tm, i, y); } else { updatey(v*2+1, tm+1, tr, i, y); } t[v].sum = (t[v*2].sum * t[v*2+1].sum) % MOD; if (t[v*2].anslg > t[v*2].lg + t[v*2+1].anslg) { t[v].ans = t[v*2].ans; t[v].anslg = t[v*2].anslg; } else { t[v].ans = (t[v*2].sum * t[v*2+1].ans) % MOD; t[v].anslg = t[v*2].lg + t[v*2+1].anslg; } t[v].lg = t[v*2].lg + t[v*2+1].lg; } int init(int N, int X[], int Y[]) { cin >> N; for (int i=0; i < N; i++) { cin >> X[i]; } for (int i=0; i < N; i++) { cin >> Y[i]; } n = (ll)N; for (int i=0; i < N; i++) { a.pb(X[i]); b.pb(Y[i]); } build(1, 0, n-1); return t[1].ans; } int updateX(int pos, int val) { ll i = (ll)pos, x = (ll)val; updatex(1, 0, n-1, i, x); return t[1].ans; } int updateY(int pos, int val) { ll i = (ll)pos, y = (ll)val; updatey(1, 0, n-1, i, y); return t[1].ans; }
#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...