| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 923063 | oblantis | 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.
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 1e9+7;
const int maxn = 5e5 + 4;
__int128 inf;
__int128 t[maxn * 4];
int it, xl;
int n;
__int128 a[maxn], b[maxn], mx[maxn * 4];
set<int> s;
void upd(int v, int l, int r){
if(l + 1 == r){
t[v] = a[l];
mx[v] = b[l];
return;
}
if((l + r) / 2 <= it)upd(v * 2 + 2, (l + r) / 2, r);
else upd(v * 2 + 1, l, (l + r) / 2);
t[v] = t[v * 2 + 1] * t[v * 2 + 2] % mod;
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
__int128 gm(int v, int l, int r){
if(xl <= l)return mx[v];
if(r <= xl)return 0;
return max(gm(v * 2 + 1, l, (l + r) / 2), gm(v * 2 + 2, (l + r) / 2, r));
}
__int128 mlp(int v, int l, int r){
if(r <= xl + 1)return t[v];
if(xl < l) return 1;
return mlp(v * 2 + 1, l, (l + r) / 2) * mlp(v * 2 + 2, (l + r) / 2, r) % mod;
}
int get(){
xl = 0;
__int128 ans = gm(0, 0, n), p = 1, k = 0;
if(s.empty()){
return ans;
}
auto i = --s.end();
while(1){
xl = *i;
__int128 nx = gm(0, 0, n);
if(p * k < nx){
ans = nx * mlp(0, 0, n) % mod;
k = nx;
}
p *= a[xl];
if(p > inf)break;
if(i == s.begin())break;
--i;
}
xl = 0;
__int128 nx = gm(0, 0, n);
if(p * k < nx)ans = nx;
return ans;
}
int init(int m, int x[], int y[]) {
inf = 1;
int wt = 40;
while(wt--)inf *= 2;
n = m;
for(int i = 0; i < n; i++){
a[i] = x[i], b[i] = y[i];
it = i;
upd(0, 0, n);
if(a[i] != 1)s.insert(i);
}
return get();
}
int updateX(int pos, int val) {
if(a[pos] == val)return get();
if(a[pos] == 1)s.insert(pos);
else if(val == 1)s.erase(pos);
it = pos;
a[it] = val;
upd(0, 0, n);
return get();
}
int updateY(int pos, int val) {
it = pos;
b[it] = val;
upd(0, 0, n);
return get();
}
//int main(){
//int n;
//cin >> n;
//int x[n], y[n];
//for(int i = 0; i < n; i++)cin >> x[i];
//for(int i = 0; i < n; i++)cin >> y[i];
//cout << init(n, x, y) << '\n';
//int m;
//cin >> m;
//while(m--){
//int wt, pos, val;
//cin >> wt >> pos >> val;
//if(wt == 2)cout << updateY(pos,val) << '\n';
//else cout << updateX(pos,val) << '\n';
//}
//return 0;
}