Submission #247673

#TimeUsernameProblemLanguageResultExecution timeMemory
247673fivefourthreeoneHorses (IOI15_horses)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define owo(i,a, b) for(int i=(a); i<(b); ++i) #define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i) #define senpai push_back #define ttgl pair<int, int> #define ayaya cout<<"debug"<<endl using namespace std; using ll = long long; using ld = long double; const ll MOD = 1e9+7; const double PI = acos(-1); const int INF = 0x3f3f3f3f; const int NINF = 0x3f3f3f40; const ll INFLL = 0x3f3f3f3f3f3f3f3f; const ll NINFLL = 0x3f3f3f3f3f3f3f40; const int mxN = 500001; int n; set<int> good; int startpos = -1; int sgmax[2*mxN]; ll ans = 1; ll x[mxN]; int y[mxN]; void build() { for(int i=n; i<2*n; ++i) sgmax[i] = y[i-n]; for(int i=n-1; i>0; --i) sgmax[i] = max(sgmax[i<<1], sgmax[i<<1|1]); } void upd(int p, int val) { for(sgmax[p+=n] =val; p>0; p>>=1) sgmax[p>>1] = max(sgmax[p], sgmax[p^1]); } int qmax(int l, int r) { r++; int res = 0; for(l+=n, r+=n; l<r; l>>=1, r>>=1) { if(l&1)res = max(res, sgmax[l++]); if(r&1)res = max(res, sgmax[--r]); } return res; } ll binpow(ll a, ll b) { ll res = 1; while(b){ if(b&1) res = (res*a)%MOD; b>>=1; a = (a*a)%MOD;}return res;} ll modInv(ll a) {return binpow(a, MOD-2);} ll solve() { if(startpos==-1) return qmax(0, n-1); ll best= 1; ll curr = 1; ll partans = 1; int start = startpos; auto it = --good.end(); while(partans<(ll)(1e9+7)&&start>startpos) { partans*=x[*it]; start = *it; if(it==good.begin())break; it--; } partans = 1; owo(i, startpos, start){ partans = partans*x[i]%MOD; } it = good.lower_bound(start); while(it!=good.end()) { curr = curr*(x[*it]); best = max(best, (ll)qmax(*it, next(it)==good.end() ? n-1 : *next(it))*curr); it++; } return ((ans*partans)%MOD*best%MOD); } ll init(int N, int X[], int Y[]) { n = N; owo(i, 0, mxN) { x[i] = X[i]; y[i] = Y[i]; } build(); owo(i, 0, n) { if(x[i]>1) good.insert(i); } auto it = --good.end(); int num = 60; while(num) { num--; if(it==good.begin())break; it--; } startpos = *it; owo(i, 0, startpos) { ans = (ans*x[i])%MOD; } return solve(); } ll updateX(int pos, int val) { if(x[pos]==1&&val!=1) { good.insert(pos); if(pos<startpos) { ans = (ans*val)%MOD; }else if(pos>startpos){ ans = (ans*x[startpos]%MOD); auto it = good.upper_bound(startpos); startpos = (it==good.end() ? -1 : *it); } //cout<<ans<<" "<<startpos<<"\n"; }else if(x[pos]!=1&&val==1) { auto it = good.find(pos); if(pos<startpos) { ans = (ans*modInv(x[pos]))%MOD; }else if(pos>=startpos) { if(it!=good.begin()) { startpos = *prev(it); } } good.erase(good.find(pos)); }else if(x[pos]!=1) { if(pos<startpos) { ans = (ans*modInv(x[pos]))%MOD; ans = (ans*val)%MOD; } } x[pos] = val; return solve(); } ll updateY(int pos, int val) { upd(pos, val); return solve(); } /*int main() { //freopen("filename.in", "r", stdin); //freopen("filename.out", "w", stdout); cin.tie(0)->sync_with_stdio(0); int tempn; int tempx[mxN]; int tempy[mxN]; cin>>tempn; owo(i, 0, tempn) { cin>>tempx[i]; } owo(i,0, tempn) { cin>>tempy[i]; } cout<<init(tempn, tempx, tempy)<<"\n"; int q; int a, b; cin>>q; while(q--) { cin>>a>>b; cout<<updateX(a, b)<<"\n"; } return 0; }

Compilation message (stderr)

horses.cpp:126:1: error: unterminated comment
 /*int main()
 ^