| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 153942 | ivandasfs | Horses (IOI15_horses) | C++14 | 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 <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
vector <ll> X;
vector <ll> Y;
set <pair<int, int> > jed;
ll umno[3000005];
ll maxi[3000005];
int n;
int off;
void umno_update(int node, ll val) {
if (!node) return ;
if (node >= off) {
umno[node] = val;
} else {
umno[node] = (umno[node*2] * umno[node*2+1]) % MOD;
}
umno_update(node/2, val);
}
ll umno_query(int x, int y, int l, int r, int node) {
if (l>y or r<x) return 1LL;
if (l>=x and r<=y) return umno[node];
return (umno_query(x, y, l, (l+r)/2, node*2) * umno_query(x, y, (l+r)/2+1, r, node*2+1)) % MOD;
}
void maxi_update(int node, ll val) {
if (!node) return ;
if (node >= off) {
maxi[node] = val;
} else {
maxi[node] = max(maxi[node*2], maxi[node*2+1]);
}
maxi_update(node/2, val);
}
ll maxi_query(int x, int y, int l, int r, int node) {
if (l>y or r<x) return 0LL;
if (l>=x and r<=x) return maxi[node];
return max(maxi_query(x, y, l, (l+r)/2, node*2), maxi_query(x, y, (l+r)/2+1, r, node*2+1));
}
int init(int m, int *v, int *w) {
n = m;
off = 1;
while (off<n) off*=2;
for (int i=0 ; i<n ; i++) {
X.push_back(v[i]);
Y.push_back(w[i]);
umno_update(i+off, X[i]);
maxi_update(i+off, Y[i]);
}
X.push_back(-1);
for (int i=0 ; i<n ; i++) {
if (X[i]==1) {
int st = i;
while (X[i]==1) i++;
jed.insert(make_pair(st, i-1));
}
}
X.pop_back();
ll suff = 1;
bool over = false;
for (int i=n-1 ; i>=0 ; i--) {
if (over) {
return (umno_query(0, i, 0, off-1, 1) * suff) % MOD;
}
suff = max(suff * X[i], Y[i] * X[i]);
if (suff >= MOD) {
over = true;
suff %= MOD;
}
}
return suff;
}
ll calculate() {
ll suff = 1;
bool over = false;
for (int i=n-1 ; i>=0 ; i--) {
if (over) {
return (umno_query(0, i, 0, off-1, 1) * suff) % MOD;
}
if (X[i] == 1) {
set <pair<int, int> > :: iterator it = jed.lower_bound(make_pair(i, i+1));
it--;
// cout << it -> first << " " << it -> second << endl;
ll best = maxi_query(it -> first, it -> second, 0, off-1, 1);
suff = max(suff, best);
i = (it -> first);
} else {
suff = max(suff * X[i], Y[i] * X[i]);
if (suff >= MOD) {
over = true;
suff %= MOD;
}
}
// cout <<"suff = "<<suff<<endl;
}
return suff;
}
int updateX(int pos, ll val) {
int bio = X[pos];
X[pos] = val;
umno_update(pos+off, val);
if (bio == 1) {
set <pair<int, int> > :: iterator it = jed.lower_bound(make_pair(pos, 10000000));
it--;
pair <int, int> p = *it;
pair <int, int> l = make_pair(p.first, pos-1);
pair <int, int> r = make_pair(pos+1, p.second);
jed.erase(it);
if (l.first <= l.second) jed.insert(l);
if (r.first <= r.second) jed.insert(r);
}
if (val == 1) {
jed.insert(make_pair(pos, pos));
set <pair <int, int> > :: iterator l, r, it;
it = jed.lower_bound(make_pair(pos, pos));
r = it;
l = it;
if (l != jed.begin()) {
l--;
if (l -> second == pos - 1) {
pair <int, int> newp = make_pair(l -> first, pos);
jed.erase(l);
jed.erase(it);
jed.insert(newp);
it = jed.find(newp);
}
}
r++;
if (r != jed.end()) {
if (r -> first == pos+1) {
pair <int, int> newp = make_pair(it -> first, r -> second);
jed.erase(it);
jed.erase(r);
jed.insert(newp);
}
}
}
return calculate();
}
int updateY(int pos, ll val) {
Y[pos] = val;
maxi_update(pos+off, val);
return calculate();
}
/*
int main() {
int m;
cin >>m;
vector <int> a;
vector <int> b;
for (int i=0 ; i<m ; i++) {
int x;
cin >>x;
a.push_back(x);
}
for (int i=0 ; i<m ; i++) {
int x;
cin >>x;
b.push_back(x);
}
cout <<init(m, a, b)<<endl;
int q;
cin >>q;
for (int i=0 ; i<q ; i++) {
char c;
int pos, val;
cin >>c>>pos>>val;
if (c=='X') cout <<updateX(pos, val)<<endl;
else cout <<updateY(pos, val)<<endl;
}
return 0;
}
*/