제출 #206984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206984		oscarsierra12	말 (IOI15_horses)	C++14	37 / 100	716 ms	53116 KiB

horses

#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, int> pli ;
typedef pair<pli, pli> 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 mnPos[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] ;
        if ( arx[l] == 1 ) mnPos[nod] = n ;
        else mnPos[nod] = 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]] ) ;
    mnPos[nod] = min ( mnPos[lft[nod]], mnPos[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 ;
        if ( arx[l] == 1 ) mnPos[nod] = n ;
        else mnPos[nod] = l ;
        supMod[nod] = 0 ;
        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]] ;
    mnPos[nod] = min ( mnPos[lft[nod]], mnPos[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, n},{1,1}};
    if ( l == a && r == b ) return {{mx[nod],mnPos[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.ff, R.ff.ff),min(L.ff.ss, R.ff.ss)}, {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)>>1 ;
        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 psb = (l?ary[l-1]:0) ;
    ll best = 0, cur = 1 ;
    int bg = l ;
    while ( bg < n ) {
        l = query (0,0,n-1, bg+1, n-1).ff.ss ;
        best = max ( best, cur * query(0,0,n-1,bg,l-1).ff.ff * arx[bg] ) ;
        cur *= arx[bg] ;
        bg = l ;
    }
    if ( psb > best ) return (ans*psb)%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();
}

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

horses.cpp: In function 'int solve()':
horses.cpp:94:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     if ( psb > best ) return (ans*psb)%mod ;
                              ~~~~~~~~~^~~~
horses.cpp:96:22: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return (ans*best)%mod ;
            ~~~~~~~~~~^~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23