| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1099213 | Tymond | Horses (IOI15_horses) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 7;
const int BASE = (1 << 19);
int x[MAXN];
int y[MAXN];
int n;
set<int> ok;
set<pii> bad;
pii tree2[2 * BASE + 7];//max query (Y)
ll tree[2 * BASE + 7];//mnożenie modulo
ll lazy[2 * BASE + 7];//lazy mnożenie modulo
ll inv(ll a){
if(a <= 1){
return a;
}
return (ll)MOD - (ll)(MOD / a) * inv(MOD % a) % MOD;
}
void Push(int v){
tree[2 * v] = (ll)tree[2 * v] * lazy[v] % MOD;
tree[2 * v + 1] = (ll)tree[2 * v + 1] * lazy[v] % MOD;
lazy[2 * v] = (ll)lazy[2 * v] * lazy[v] % MOD;
lazy[2 * v + 1] = (ll)lazy[2 * v + 1] * lazy[v] % MOD;
lazy[v] = 1LL;
}
//find mx w tablicy y
pii getMx(int v, int l, int p, int a, int b){
if(b < l || p < a){
return {0, a};
}
if(a <= l && p <= b){
return tree2[v];
}
int mid = (l + p) / 2;
pii res1 = getMx(2 * v, l, mid, a, b);
pii res2 = getMx(2 * v + 1, mid + 1, p, a, b);
if(res1.fi > res2.fi){
return res1;
}
return res2;
}
//iloczyn xl * ... * xp
ll query(int v, int l, int p, int a){
if(l == p){
return tree[v];
}
Push(v);
int mid = (l + p) / 2;
if(a <= mid){
return query(2 * v, l, mid, a);
}else{
return query(2 * v + 1, mid + 1, p, a);
}
}
void upd(int v, int l, int p, int a, int b, ll val){
if(p < a || b < l){
return;
}
tree[v] = (ll)tree[v] * val % MOD;
if(a <= l && p <= b){
lazy[v] = (ll)lazy[v] * val % MOD;
return;
}
Push(v);
int mid = (l + p) / 2;
upd(2 * v, l, mid, ind, val);
upd(2 * v + 1, mid + 1, p, ind, val);
}
//get result
ll solve(){
vi usu;
while(sz(ok) && sz(usu) < 30){
usu.pb(*(--ok.end()));
ok.erase(--ok.end());
}
reverse(all(usu));
if(sz(usu) == 0){
return getMx(1, 0, BASE - 1, 0, n - 1).fi;
}
auto it = bad.lower_bound({usu[0], 0});
ll mul = 1LL;
int best = usu[0];
for(auto ele : usu){
mul = (ll)mul * x[ele];
if(mul > MOD){
best = ele;
mul = 1LL;
}else if((ll)mul * y[ele] > y[best]){
best = ele;
mul = 1LL;
}
if(it != bad.end() && (*it).fi == ele + 1){
pii now = getMx(1, 0, BASE - 1,(*it).fi, (*it).se);
//cout << mul << ' ' << now.fi<< ' ' << now.se << '\n';
if((ll)mul * now.fi > y[best]){
mul = 1LL;
best = now.se;
}
it++;
}
}
for(auto ele : usu){
ok.insert(ele);
}
//cout << best << ' ' << y[best] << ' ' << query(1, 0, BASE - 1, best) << '\n';
return (ll)y[best] * query(1, 0, BASE - 1, best) % MOD;
}
int init(int N, int Xn[], int Yn[]){
n = N;
for(int i = 0; i < n; i++){
x[i] = Xn[i];
y[i] = Yn[i];
}
for(int i = 1; i < 2 * BASE + 7; i++){
tree[i] = lazy[i] = 1LL;
}
ll mul = 1LL;
for(int i = 0; i < n; i++){
tree2[i + BASE] = {y[i], i};
mul = (ll)mul * x[i];
mul %= MOD;
tree[i + BASE] = mul;
}
for(int i = BASE - 1; i >= 1; i--){
tree[i] = (ll)tree[2 * i] * tree[2 * i + 1] % MOD;
if(tree2[2 * i].fi > tree2[2 * i + 1].fi){
tree2[i] = tree2[2 * i];
}else{
tree2[i] = tree2[2 * i + 1];
}
}
int i = 0;
for(i = 0; i < n; i++){
if(x[i] > 1){
ok.insert(i);
continue;
}
int b = i;
while(i + 1 < n && x[i + 1] == 1){
i++;
}
bad.insert({b, i});
}
return (int)solve();
}
int updateX(int pos, int val){
if(x[pos] == 1){
if(val == 1){
return (int)solve();
}
//prevVal == 1 ^ val > 1
auto it = bad.upper_bound({pos, 0});
--it;
pii akt = *it;
bad.erase(it);
if(akt.fi != pos){
bad.insert({akt.fi, pos - 1});
}
if(akt.se != pos){
bad.insert({pos + 1, akt.se});
}
ok.insert(pos);
upd(1, 0, BASE - 1, pos, n - 1, val);
x[pos] = val;
}else{
if(val > 1){
upd(1, 0, BASE - 1, pos, n - 1, (ll)val * inv(x[pos]) % MOD);
x[pos] = val;
return (int)solve();
}
//prevVal > 1 ^ val == 1
upd(1, 0, BASE - 1, pos, n - 1, inv(x[pos]));
x[pos] = 1;
pii d = {pos, pos};
if(sz(bad)){
auto it = bad.lower_bound({pos, 0});
if(it != bad.end() && (*it).fi == pos + 1){
d.se = (*it).se;
bad.erase(it);
}
auto it2 = bad.lower_bound({pos, 0});
if(it2 != bad.begin()){
--it2;
if((*it2).se == pos - 1){
d.fi = (*it2).fi;
bad.erase(it2);
}
}
}
bad.insert(d);
}
return (int)solve();
}
int updateY(int pos, int val){
y[pos] = val;
tree2[pos + BASE] = {val, pos};
pos += BASE;
pos /= 2;
while(pos > 0){
if(tree2[2 * pos].fi > tree2[2 * pos + 1].fi){
tree2[pos] = tree2[2 * pos];
}else{
tree2[pos] = tree2[2 * pos + 1];
}
pos /= 2;
}
return (int)solve();
}
/*int main(){
int p[3] = {2, 1, 3};
int d[3] = {3, 4, 1};
cout << init(3, p, d) << '\n';
cout << updateY(1, 2) << '\n';
return 0;
}*/