Submission #1014049

#TimeUsernameProblemLanguageResultExecution timeMemory
1014049Error404Horses (IOI15_horses)C++17
100 / 100
155 ms66384 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define f first #define s second #define pi pair<ll,ll> #define vi vector<ll> #define vd vector<double> #define vpi vector<pi> #define pb push_back #define INF 1e18 #define endl '\n' //#define int ll #define pii pair<pi,ll> const int mod = 1e9+7; vd x, y; vi ox, oy; const int MAX = 500000; int n; struct dt { double sum, pref; ll mulx,ans; }; dt t[MAX*4]; dt make_data(int i){ dt a; a.sum = x[i]; a.mulx = ox[i]; a.pref = x[i] + y[i]; a.ans = (ox[i]*oy[i])%mod; return a; } dt combine(dt a, dt b){ dt hold; hold.sum = a.sum+ b.sum; hold.mulx = ((a.mulx % mod) * (b.mulx % mod))%mod; if(a.pref > a.sum+b.pref){ hold.pref = a.pref; hold.ans = a.ans; } else{ hold.pref = a.sum + b.pref; hold.ans = (a.mulx * b.ans)%mod; } return hold; } void build(int v,int l,int r){ if(l==r){ t[v] = make_data(l); return; } int m = (l+r)/2; build(v*2,l,m); build(v*2+1,m+1,r); t[v] = combine(t[v*2],t[v*2+1]); } void update(int v, int l,int r, int pos){ if(l==r){ t[v]= make_data(l); return; } int m = (l+r)/2; if(pos<=m) update(v*2,l,m,pos); else update(v*2+1,m+1,r,pos); t[v] = combine(t[v*2],t[v*2+1]); } ll init(int N, int a[], int b[]){ n = N; x.resize(n+1); y.resize(n+1); ox.resize(n+1); oy.resize(n+1); x[0]=0; y[0]=0; for(int i =1 ; i <= n; i++){ ox[i] = a[i-1]; oy[i] = b[i-1]; x[i] =log10(ox[i]); y[i] = log10(oy[i]); } build(1,1,n); return (t[1].ans%mod); } ll updateX(int pos,int val){ pos ++; x[pos] = log10(val); ox[pos]= val; update(1,1,n,pos); return (t[1].ans%mod); } ll updateY(int pos,int val){ pos++; y[pos] = log10(val); oy[pos] = val; update(1,1,n,pos); return (t[1].ans%mod); }
#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...