제출 #297464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297464		humbertoyusta	말 (IOI15_horses)	C++14	17 / 100	1554 ms	33448 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 500050
#define mod 1000000007
#define ll long long
#define f first
#define s second
#define ii pair<ll,ll>
#define db(x) cerr << #x << ": " << (x) << '\n';

struct node{
    ll mx, my, px;
} st[maxn*4];
int x[maxn], y[maxn], n;

node join(node a,node b){
    return { max( a.mx , b.mx ) , max( a.my , b.my ) , a.px * b.px % mod };
}

void build(int nod,int l,int r){

    if( l == r ){ st[nod] = { x[l] , y[l] , x[l] }; return; }

    int mi = ( l + r ) >> 1;
        build(2*nod,l,mi);
        build(2*nod+1,mi+1,r);

    st[nod] = join( st[2*nod] , st[2*nod+1] );
}

void update(int nod,int l,int r,int id){

    if( l == r ){ st[nod] = { x[l] , y[l] , x[l] }; return; }

    int mi = ( l + r ) >> 1;
    if( id <= mi ) update(2*nod,l,mi,id);
        else update(2*nod+1,mi+1,r,id);

    st[nod] = join( st[2*nod] , st[2*nod+1] );
}

int queryx(int nod,int l,int r,int xx,int yy){

    if( l > yy || r < xx || l > r ) return 0;

    if( l == r ){
        if( st[nod].mx > 1 ) return l;
        return 0;
    }

    int mi = ( l + r ) >> 1;

    if( l >= xx && r <= yy ){
        if( st[2*nod+1].mx > 1 )
            return queryx(2*nod+1,mi+1,r,xx,yy);
        if( st[2*nod].mx > 1 )
            return queryx(2*nod,l,mi,xx,yy);
        return 0;
    }

    return max( queryx(2*nod,l,mi,xx,yy) , queryx(2*nod+1,mi+1,r,xx,yy) );
}

node queryy(int nod,int l,int r,int xx,int yy){

    if( l > yy || r < xx || l > r ) return { 0 , 0 , 1 };

    if( l >= xx && r <= yy ) return st[nod];

    int mi = ( l + r ) >> 1;

    return join( queryy(2*nod,l,mi,xx,yy) , queryy(2*nod+1,mi+1,r,xx,yy) );
}

int solve(){
    ll res = x[n] * y[n];
    int id = n;
    bool moduled = 0;
    if( res < mod ){
        for(int i=1; i<=32; i++){

            int nid = queryx(1,1,n,1,id-1);
            if( nid == 0 ) break;

            node f = queryy(1,1,n,nid,id-1);
            res = max( res , f.my );
            res *= f.px;

            id = nid;
            if( res >= mod ){
                moduled = 1;
                res %= mod;
                break;
            }
        }
    }
    else{
        res %= mod;
        moduled = 1;
    }

    node cc = queryy(1,1,n,1,id-1);

    res *= cc.px;
    if( res >= mod ){
        res %= mod;
        moduled = 1;
    }

    if( !moduled ){
        res = max( res , cc.my );
    }

    return res;
}

int init(int N, int X[], int Y[]) {

    n = N;

	for(int i=0; i<N; i++){
        x[i+1] = X[i];
        y[i+1] = Y[i];
	}

	build(1,1,N);

	return solve();
}

int updateX(int pos, int val) {

	x[pos+1] = val;
	update(1,1,n,pos+1);

	return solve();
}

int updateY(int pos, int val) {

	y[pos+1] = val;
	update(1,1,n,pos+1);

	return solve();
}

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

horses.cpp: In function 'int solve()':
horses.cpp:115:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |     return res;
      |            ^~~

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