Submission #133605

#TimeUsernameProblemLanguageResultExecution timeMemory
133605ckodserHorses (IOI15_horses)C++14
100 / 100
862 ms49256 KiB
#include "horses.h" #include<bits/stdc++.h> #define ll long long #define pb push_back #define ld long double #define mp make_pair #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll maxn=5e5+500; const ll inf=1e9+6; const ll mod=1e9+7; ll modizarb(long long a,long long b){return (a*b)%mod;} ll y[maxn]; ll seg[maxn*4]; void bild(ll l,ll r,ll node){ if(l+1==r){ seg[node]=y[l]; return; } ll mid=(l+r)/2; bild(l,mid,2*node); bild(mid,r,2*node+1); seg[node]=max(seg[2*node],seg[2*node+1]); } void update(ll l,ll r,ll node,ll pos){ if(l+1==r){ seg[node]=y[l]; return; } ll mid=(l+r)/2; if(pos<mid) update(l,mid,2*node,pos); else update(mid,r,2*node+1,pos); seg[node]=max(seg[2*node],seg[2*node+1]); } ll findMx(ll l,ll r,ll L,ll R,ll node){ if(l<=L && R<=r){ return seg[node]; } if(r<=L || R<=l){ return 0; } ll mid=(L+R)/2; return max(findMx(l,r,L,mid,2*node),findMx(l,r,mid,R,2*node+1)); } set<ll> st; ll x[maxn]; ll rx[maxn]; ll n,Z; ll poww(ll a,ll b){ ll ans=1; while(b){ if(b&1){ ans=(ans*a)%mod; } b>>=1; a=(a*a)%mod; } return ans; } ll findAns(){ auto it=st.end(); ll last=n; ll ans=0; ll t=Z; bool br=0; while(it!=st.begin()){ it--; ll v=(*it); ll yy=findMx(v,last,0,n,1); ans=max(ans,yy); if(ans*x[v]>inf){ br=1; break; } ans*=x[v]; t=modizarb(t,rx[v]); last=v; } if(!br){ ll v=0; ll yy=findMx(v,last,0,n,1); ans=max(ans,yy); } return modizarb(ans,t); } int init(int N, int X[], int Y[]){ n=N; Z=1; for(ll i=0;i<n;i++){ x[i]=X[i]; Z=modizarb(Z,X[i]); rx[i]=poww(x[i],mod-2); y[i]=Y[i]; if(x[i]!=1)st.insert(i); } bild(0,n,1); return findAns(); } int updateX(int pos, int val) { Z=modizarb(Z,rx[pos]); if(x[pos]!=1 && val==1){ st.erase(pos); } if(x[pos]==1 && val!=1){ st.insert(pos); } x[pos]=val; Z=modizarb(Z,val); rx[pos]=poww(x[pos],mod-2); return findAns(); } int updateY(int pos, int val){ y[pos]=val; update(0,n,1,pos); return findAns(); }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:108:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return findAns();
            ~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:121:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return findAns();
            ~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:126:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return findAns();
            ~~~~~~~^~
#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...