Submission #206931

#TimeUsernameProblemLanguageResultExecution timeMemory
206931oscarsierra12Horses (IOI15_horses)C++14
Compilation error
0 ms0 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,int>> iii ; const int N = 1e7 ; const int o = 5e5+2 ; const int mod = 1e9+7 ; int lft[N], rg[N]; ll mx[N], mult[N] ; int supMod[N] ; int cntNode = 0 ; int arx[o], ary[o] ; int n ; void build ( int nod, int l, int r ) { int mid = (l+r)/2 ; if ( l == r ) { mx [nod] = ary[l] ; mult [nod] = arx[l] ; 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 ( int nod, int l, int r, int a, int x, int y ) { int 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 ( int nod, int l, int r, int a, int b ) { int 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 )}}; } int solve () { int l = 0, r = n-1 ; while ( l < r ) { int 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 ; int lst = l-1 ; ll psb = (l?x[l-1] * y[l-1]:0) ; ll best = 0, cur = 1 ; int bg = l ; while ( bg < n ) { l = bg, r = n ; while ( l < r ) { int mid = (l+r)/2 ; if ( query(0,0,n-1,bg,mid).ss.ff == x[bg] ) l = mid+1 ; else r = mid ; } best = max ( best, cur * query(0,0,n-1,bg,l-1).ff * x[bg] ) ; cur *= x[bg] ; bg = l ; } if ( psb > best ) return (ans*y[lst])%mod ; best %= mod ; return (ans*best)%mod ; } int init(int Ne, int X[], int Y[]) { for ( int 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(); }

Compilation message (stderr)

horses.cpp: In function 'int solve()':
horses.cpp:76:17: error: 'x' was not declared in this scope
     ll psb = (l?x[l-1] * y[l-1]:0) ;
                 ^
horses.cpp:76:26: error: 'y' was not declared in this scope
     ll psb = (l?x[l-1] * y[l-1]:0) ;
                          ^
horses.cpp:92:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return (ans*best)%mod ;
            ~~~~~~~~~~^~~~