Submission #1206382

#TimeUsernameProblemLanguageResultExecution timeMemory
1206382peraHorses (IOI15_horses)C++20
17 / 100
1597 ms51392 KiB
#include<bits/stdc++.h> #include "horses.h" #define LL long long using namespace std; const int N_MAX = 5E5 + 1; const LL mod = 1E9 + 7 , oo = 1E9; int n; set<int> S; vector<LL> x(N_MAX) , y(N_MAX); template<typename T> struct segment_tree{ vector<T> st , a; T neutral; int size; function<T(T , T)> join; segment_tree(int _size , vector<T> _a , T _neutral , function<T(T , T)> _join){ join = _join; size = _size; neutral = _neutral; a = _a; st = vector<T>(2 * _size , _neutral); build(); } segment_tree(int _size , T _neutral , function<T(T , T)> _join){ join = _join; size = _size; neutral = _neutral; st = vector<T>(2 * _size , _neutral); } void build(){ for(int i = 2 * size - 1;i > 0;i --){ st[i] = (i < size ? join(st[i << 1] , st[i << 1 | 1]) : a[i - size + 1]); } } void point_update(int x , T val){ --x; st[x + size] = join(val , st[x + size]); for(x += size;x > 1;x >>= 1){ st[x >> 1] = join(st[x] , st[x ^ 1]); } } void point_assign(int x , T val){ --x; st[x + size] = val; for(x += size;x > 1;x >>= 1){ st[x >> 1] = join(st[x] , st[x ^ 1]); } } T range_query(int l , int r){ if(l > r){ return neutral; } --l; T resL = neutral , resR = neutral; for(l += size , r += size;l < r;l >>= 1 , r >>= 1){ if(l & 1){ resL = join(resL , st[l++]); } if(r & 1){ resR = join(st[--r] , resR); } } return join(resL , resR); } }; LL stf(LL x , LL y){ return max(x , y); }; LL sff(LL x , LL y){ return x * y % mod; }; segment_tree<LL> st(N_MAX , 0 , stf); segment_tree<LL> sf(N_MAX , 1 , sff); int calc(){ LL prd = 1 , j = -1; for(int i = n - 1;i > 0;i --){ prd *= x[i]; if(prd > 1E9){ j = i; break; } } prd = 1; LL bst = 0 , a; for(int i = j + 1;i < n;i ++){ prd *= x[i]; if(prd * y[i] > bst){ bst = prd * y[i]; a = i; } } int ans = 1; for(int i = 0;i <= a;i ++){ ans = ans * x[i] % mod; } ans = ans * y[a] % mod; return ans; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0;i < N;i ++){ x[i] = X[i]; y[i] = Y[i]; if(X[i] > 1){ S.insert(i); } sf.point_assign(i + 1 , X[i]); st.point_assign(i + 1 , Y[i]); } return calc(); } int updateX(int pos, int val) { if(x[pos] > 1){ S.erase(pos); } x[pos] = val; if(x[pos] > 1){ S.insert(pos); } sf.point_assign(pos + 1, x[pos]); return calc(); } int updateY(int pos, int val) { y[pos] = val; st.point_assign(pos + 1 , val); return calc(); }
#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...