Submission #297454

#	Time	Username	Problem	Language	Result	Execution time	Memory
297454		humbertoyusta	Horses (IOI15_horses)	C++14	0 / 100	1589 ms	33860 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optmize ("Ofast")
#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 x,int y){

    if( l > y || r < x || l > r ) return 0;

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

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

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

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

node queryy(int nod,int l,int r,int x,int y){

    if( l > y || r < x || l > r ) return { 0 , 0 , 1 };

    if( l >= x && r <= y ) return st[nod];

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

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

int solve(){
    ll res = x[n] * y[n];
    int id = n;
    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 ){
                res %= mod;
                break;
            }
        }
    }
    return res * queryy(1,1,n,1,id-1).px % mod;
}

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();
}

Compilation message (stderr)

horses.cpp:4: warning: ignoring #pragma GCC optmize [-Wunknown-pragmas]
    4 | #pragma GCC optmize ("Ofast")
      | 
horses.cpp: In function 'int queryx(int, int, int, int, int)':
horses.cpp:44:43: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   44 | int queryx(int nod,int l,int r,int x,int y){
      |                                           ^
horses.cpp:16:14: note: shadowed declaration is here
   16 | int x[maxn], y[maxn], n;
      |              ^
horses.cpp:44:43: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   44 | int queryx(int nod,int l,int r,int x,int y){
      |                                           ^
horses.cpp:16:5: note: shadowed declaration is here
   16 | int x[maxn], y[maxn], n;
      |     ^
horses.cpp: In function 'node queryy(int, int, int, int, int)':
horses.cpp:66:44: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   66 | node queryy(int nod,int l,int r,int x,int y){
      |                                            ^
horses.cpp:16:14: note: shadowed declaration is here
   16 | int x[maxn], y[maxn], n;
      |              ^
horses.cpp:66:44: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   66 | node queryy(int nod,int l,int r,int x,int y){
      |                                            ^
horses.cpp:16:5: note: shadowed declaration is here
   16 | int x[maxn], y[maxn], n;
      |     ^
horses.cpp: In function 'int solve()':
horses.cpp:97:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |     return res * queryy(1,1,n,1,id-1).px % mod;
      |                                          ^

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