Submission #238876

#	Time	Username	Problem	Language	Result	Execution time	Memory
238876		Ruxandra985	Horses (IOI15_horses)	C++14	37 / 100	492 ms	56312 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
#define DIMN 500010
#define MOD 1000000007
using namespace std;
int nt , xt[DIMN] , yt[DIMN];

set <  pair <   pair <int , int> , pair <int , int>    >  > state;

set <  pair <   pair <int , int> , pair <int , int>    >  > :: iterator aux , it;

set <  pair <   pair <int , int> , pair <int , int>    >  > :: reverse_iterator rit;


int aint[4*DIMN] , prod[4 * DIMN];
void build (int nod , int st , int dr){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod] = st;
        prod[nod] = xt[st];
        return;
    }
    build (2 * nod , st , mid);
    build (2 * nod + 1 , mid + 1 , dr);

    if (yt[aint[2 * nod]] > yt[aint[2 * nod + 1]])
        aint[nod] = aint[2 * nod];
    else aint[nod] = aint[2 * nod + 1];

    prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;


}

void update_prod (int nod , int st , int dr , int pos , int val){
    int mid = (st + dr)/2;

    if (st == dr){
        prod[nod] = val;
        return;
    }

    if (pos <= mid)
        update_prod(2 * nod , st , mid , pos , val);
    else
        update_prod(2 * nod + 1 , mid + 1 , dr , pos , val);

    prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;


}


int query (int nod , int st , int dr , int x , int y){
    int mid = (st + dr)/2 , maxi = 0 , val;

    if (x <= st && dr <= y){
        return aint[nod];
    }

    if (x <= mid){
        val = query(2 * nod , st , mid , x , y);
        if (maxi == 0 || yt[maxi] < yt[val])
            maxi = val;
    }
    if (mid + 1 <= y){
        val = query(2 * nod + 1 , mid + 1 , dr , x , y);
        if (maxi == 0 || yt[maxi] < yt[val])
            maxi = val;
    }

    return maxi;


}

int query_prod (int nod , int st , int dr , int x , int y){
    int mid = (st + dr)/2 , sol = 1;

    if (x <= st && dr <= y){
        return prod[nod];
    }

    if (x <= mid)
        sol = (1LL * sol * query_prod(2 * nod , st , mid , x , y))%MOD;
    if (mid + 1 <= y)
        sol = (1LL * sol * query_prod(2 * nod + 1 , mid + 1 , dr , x , y))%MOD;

    return sol;


}

void update (int nod , int st , int dr , int pos , int val){
    int mid = (st + dr)/2;


    if (st == dr){
        aint[nod] = pos;
        return;
    }

    if (pos <= mid)
        update(2 * nod , st , mid , pos , val);
    else
        update(2 * nod + 1 , mid + 1 , dr , pos , val);

    if (yt[aint[2 * nod]] > yt[aint[2 * nod + 1]])
        aint[nod] = aint[2 * nod];
    else aint[nod] = aint[2 * nod + 1];

}



int solve_current_state (){

    int idx , inc , ymax , taken;
    long long have_sol;

    /// !! solutia e in ultimele 60 de pozitii
    have_sol = 0;
    idx = 0;
    for (rit = state.rbegin() , taken = 1 ; rit != state.rend() && taken <= 60; rit++ , taken++){

        inc = (*rit).first.first;
        ymax = (*rit).second.second;


        if (have_sol == 0){
            have_sol = 1LL * xt[inc] * yt[ymax];
            idx = ymax;
        }
        else {

            if (yt[ymax] < have_sol){
                if (have_sol <= 1000000000)
                    have_sol = (have_sol * xt[ymax]);
            }
            else {
                have_sol = 1LL * xt[inc] * yt[ymax];
                idx = ymax;
            }

        }


    }

    return (1LL * query_prod (1 , 0 , nt - 1 , 0 , idx) * yt[idx])%MOD;


}



int init(int n, int x[], int y[]){
    int i , inc , sf , ymax;
    nt = n;

    for (i = 0 ; i < n ; i++){
        xt[i] = x[i];
        yt[i] = y[i];
    }


    for (i = 0 ; i < n ; i++){

        if (x[i] != 1){

            state.insert(make_pair(  make_pair(i , i) , make_pair(x[i] , i)  ));

        }
        else {
            inc = i;
            sf = i;
            ymax = i;
            while (sf + 1 < n && x[sf + 1] == 1){

                if (y[ymax] < y[sf + 1])
                    ymax = sf + 1;
                sf++;
            }

            state.insert(make_pair(  make_pair(inc , sf) , make_pair(1 , ymax)  ));

            i = sf;

        }

    }

    build (1 , 0 , nt - 1);

    return solve_current_state();

}
int updateX(int pos, int val){

    int inc , sf , vcurr , ymax , inc2 , sf2 , ymax2;

    it = state.upper_bound(make_pair (   make_pair(pos , nt) , make_pair(0 , 0)    ));
    it--;

    inc = (*it).first.first;
    sf = (*it).first.second;
    vcurr = (*it).second.first;
    ymax = (*it).second.second;



    if (val == 1){ /// cazul cand poate se prelungeste un interval de 1
                   /// , sau se form unul nou

        if (vcurr != 1){

            vcurr = 1;
            aux = it;
            aux--;

            if (it != state.begin() && (*aux).second.first == 1){ /// aux exista

                /// ai un interval de 1 la stanga

                inc2 = (*aux).first.first;
                sf2 = (*aux).first.second;
                ymax2 = (*aux).second.second;

                if (yt[ymax] < yt[ymax2])
                    ymax = ymax2;

                inc = inc2;

                state.erase(aux);


            }


            aux = it;
            aux++;

            if (aux != state.end() && (*aux).second.first == 1){

                /// ai un interval de 1 la dreapta

                inc2 = (*aux).first.first;
                sf2 = (*aux).first.second;
                ymax2 = (*aux).second.second;


                if (yt[ymax] < yt[ymax2])
                    ymax = ymax2;

                sf = sf2;

                state.erase(aux);

            }

            state.erase(it);

            state.insert(make_pair(  make_pair(inc , sf) , make_pair(1 , ymax)  ));

        }


    }
    else { /// cazul cand se destrama un interval de 1, sau doar se updateaza o val

        if (vcurr != 1){ /// se updateaza o valoare normala

            state.erase(it);
            state.insert(make_pair(  make_pair(inc , sf) , make_pair(val , ymax)  ));

        }
        else { /// se destrama un interval
            state.erase(it);
            state.insert(make_pair(  make_pair(pos , pos) , make_pair(val , pos)  ));


            if (inc < pos){

                ymax = query (1 , 0 , nt - 1 , inc , pos - 1);
                state.insert(make_pair(  make_pair(inc , pos - 1) , make_pair(1 , ymax)  ));

            }

            if (pos < sf){


                ymax = query (1 , 0 , nt - 1 , pos + 1 , sf);
                state.insert(make_pair(  make_pair(pos + 1 , sf) , make_pair(1 , ymax)  ));

            }

        }

    }


    xt[pos] = val;
    update_prod (1 , 0 , nt - 1 , pos , val);

    return solve_current_state();
}
int updateY(int pos, int val){

    int inc , sf , vcurr , ymax;
    it = state.upper_bound(make_pair (   make_pair(pos , nt) , make_pair(0 , 0)    ));
    it--;

    inc = (*it).first.first;
    sf = (*it).first.second;
    vcurr = (*it).second.first;
    ymax = (*it).second.second;

    state.erase(it);


    yt[pos] = val;

    update (1 , 0 , nt - 1 , pos , val);

    ymax = query(1 , 0 , nt - 1 , inc , sf);

    state.insert(make_pair(   make_pair(inc , sf) , make_pair(vcurr , ymax)   ));


    return solve_current_state();
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:31:58: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;
                                                          ^
horses.cpp: In function 'void update_prod(int, int, int, int, int)':
horses.cpp:49:58: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     prod[nod] = (1LL * prod[2 * nod] * prod[2 * nod + 1])%MOD;
                                                          ^
horses.cpp: In function 'int query_prod(int, int, int, int, int)':
horses.cpp:86:67: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         sol = (1LL * sol * query_prod(2 * nod , st , mid , x , y))%MOD;
                                                                   ^
horses.cpp:88:75: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         sol = (1LL * sol * query_prod(2 * nod + 1 , mid + 1 , dr , x , y))%MOD;
                                                                           ^
horses.cpp: In function 'int solve_current_state()':
horses.cpp:151:67: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (1LL * query_prod (1 , 0 , nt - 1 , 0 , idx) * yt[idx])%MOD;
                                                                   ^

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