제출 #1206374

#제출 시각아이디문제언어결과실행 시간메모리
1206374pera말 (IOI15_horses)C++20
17 / 100
260 ms48148 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); 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(){ if(S.empty()){ return st.range_query(1 , n); } LL val = 1; auto it = --S.end(); vector<int> v; while(true){ val *= x[*it]; if(val > oo){ break; } v.emplace_back(*it); if(it == S.begin()){ break; } --it; } reverse(v.begin() , v.end()); LL bst = -1 , prd = 1; int j , sz = (int)v.size(); vector<int> vY(sz); for(int i = 0;i < sz;i ++){ prd *= x[v[i]]; vY[i] = (i < sz - 1 ? st.range_query(v[i] + 1 , v[i + 1]) : st.range_query(v[i] + 1 , n)); if(prd * vY[i] > bst){ bst = prd * vY[i]; j = i; } } return sf.range_query(1 , v[j] + 1) * vY[j] % mod; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0;i < N;i ++){ x[i] = X[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) { 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...