제출 #206939

#제출 시각아이디문제언어결과실행 시간메모리
206939oscarsierra12말 (IOI15_horses)C++14
17 / 100
1511 ms52392 KiB
#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 ; } int init(int Ne, int X[], int 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(); } int updateX(int pos, int val) { update ( 0,0,n-1,pos,val,ary[pos]) ; arx[pos] = val ; return solve(); } int updateY(int pos, int val) { update ( 0,0,n-1,pos,arx[pos],val) ; ary[pos] = val ; return solve(); }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:17: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return solve();
            ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:113:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
#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...