Submission #238868

#TimeUsernameProblemLanguageResultExecution timeMemory
238868Ruxandra985Horses (IOI15_horses)C++14
0 / 100
264 ms50040 KiB
#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 have_sol , idx , inc , ymax , taken; /// !! 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 , 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; return solve_current_state(); } int updateY(int pos, int val){ yt[pos] = val; update (1 , 0 , nt , pos , val); 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:130:38: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             have_sol = 1LL * xt[inc] * yt[ymax];
                        ~~~~~~~~~~~~~~^~~~~~~~~~
horses.cpp:140:42: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
                 have_sol = 1LL * xt[inc] * yt[ymax];
                            ~~~~~~~~~~~~~~^~~~~~~~~~
horses.cpp:149:63: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return (1LL * query_prod (1 , 0 , nt , 0 , idx) * yt[idx])%MOD;
                                                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...