| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 206938 | oscarsierra12 | 말 (IOI15_horses) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "horses.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std ;
typedef long long ll ;
typedef pair<ll, pair<ll,ll>> iii ;
const ll N = 1e7 ;
const ll o = 5e5+2 ;
const ll mod = 1e9+7 ;
ll lft[N], rg[N];
ll mx[N], mult[N] ;
ll supMod[N] ;
ll cntNode = 0 ;
ll arx[o], ary[o] ;
ll n ;
void build ( ll nod, ll l, ll r ) {
ll mid = (l+r)/2 ;
if ( l == r ) {
mx [nod] = ary[l] ;
mult [nod] = arx[l] ;
supMod[nod] = 0 ;
return ;
}
build ( lft[nod] = ++cntNode , l, mid ) ;
build ( rg[nod] = ++cntNode , mid+1, r ) ;
mx[nod] = max ( mx[lft[nod]], mx[rg[nod]] ) ;
mult[nod] = mult[lft[nod]] * mult[rg[nod]] ;
if ( mult[nod] > mod ) supMod[nod] = 1 ;
else supMod[nod] = (supMod[lft[nod]] || supMod[rg[nod]]) ;
mult[nod] %= mod ;
}
void update ( ll nod, ll l, ll r, ll a, ll x, ll y ) {
ll mid = (l+r)/2 ;
if ( l == a && r == a ) {
mx[nod] = y ;
mult[nod] = x ;
return ;
}
if ( a <= mid ) update ( lft[nod], l, mid, a, x, y ) ;
else update ( rg[nod], mid+1, r, a, x, y ) ;
mx[nod] = max ( mx[lft[nod]], mx[rg[nod]] ) ;
mult[nod] = mult[lft[nod]] * mult[rg[nod]] ;
if ( mult[nod] > mod ) supMod[nod] = 1 ;
else supMod[nod] = (supMod[lft[nod]] || supMod[rg[nod]]) ;
mult[nod] %= mod ;
}
iii query ( ll nod, ll l, ll r, ll a, ll b ) {
ll mid = (l+r)/2 ;
if ( a > b ) return {1,{1,1}};
if ( l == a && r == b ) return {mx[nod], {mult[nod], supMod[nod]}} ;
if ( b <= mid ) return query ( lft[nod], l, mid, a, b ) ;
if ( a > mid ) return query ( rg[nod], mid+1, r, a, b ) ;
iii L = query ( lft[nod], l, mid, a, mid ) ;
iii R = query ( rg[nod], mid+1, r, mid+1, b ) ;
return {max (L.ff, R.ff), {1ll*(L.ss.ff * R.ss.ff)%mod, (L.ss.ff * R.ss.ff > mod || L.ss.ss || R.ss.ss )}};
}
ll solve () {
ll l = 0, r = n-1 ;
while ( l < r ) {
ll mid = (l+r) / 2 ;
if ( query(0,0,n-1,mid,n-1).ss.ss ) l = mid+1 ;
else r = mid ;
}
ll ans = query(0,0,n-1,0,l-1).ss.ff ;
ll lst = l-1 ;
ll psb = (l?1ll*arx[l-1] * ary[l-1]:0) ;
ll best = 0, cur = 1 ;
ll bg = l ;
while ( bg < n ) {
l = bg, r = n ;
while ( l < r ) {
ll mid = (l+r)/2 ;
if ( query(0,0,n-1,bg,mid).ss.ff == arx[bg] ) l = mid+1 ;
else r = mid ;
}
best = max ( best, cur * query(0,0,n-1,bg,l-1).ff * arx[bg] ) ;
cur *= arx[bg] ;
bg = l ;
}
if ( psb > best ) return (ans*ary[lst])%mod ;
best %= mod ;
return (ans*best)%mod ;
}
ll init(ll Ne, ll X[], ll Y[]) {
for ( ll i = 0 ; i < Ne; ++i )
arx[i] = X[i], ary[i] = Y[i] ;
n = Ne ;
build ( 0,0,n-1 ) ;
return solve();
}
ll updateX(ll pos, ll val) {
update ( 0,0,n-1,pos,val,ary[pos]) ;
arx[pos] = val ;
return solve();
}
ll updateY(ll pos, ll val) {
update ( 0,0,n-1,pos,arx[pos],val) ;
ary[pos] = val ;
return solve();
}