| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 274397 | A02 | 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 "horses.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>
#include <math.h>
using namespace std;
long long prime = 1000000007;
long long mod_exp(long long a, long long k){
if (k == 0){
return 1;
}
if (k == 1){
return a;
}
long long a1 = mod_exp(a, k / 2);
if (k % 2 == 1){
return (((a1 * a1) % prime) * a) % prime;
}
return (a1 * a1) % prime;
}
void updateModSegTree(vector<long long> &tree, int p, long long t){
int N = tree.size() / 2;
tree[p + N] = (tree[p + N] * t) % prime;
for (p = (p + N) / 2; p > 0; p = p / 2){
tree[p] = (tree[2 * p] * tree[2 * p + 1]) % prime;
}
}
long long queryModSegTree(vector<long long> &tree, int l, int r){
int N = tree.size() / 2;
long long total = 1;
for (l += N, r += N; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
total = (total * tree[l++]) % prime;
}
if (r % 2 == 1){
total = (total * tree[--r]) % prime;
}
}
return total;
}
void updateMaxSegTree(vector<pair<long long, int> > &tree, int p, long long t){
int N = tree.size() / 2;
tree[p + N].first = t;
for (p = (p + N) / 2; p > 0; p = p / 2){
tree[p].second = tree[2 * p + 1].second;
if (tree[2 * p].first > tree[2 * p + 1].first){
tree[p].second = tree[2 * p].second;
}
tree[p].first = max(tree[2 * p].first, tree[2 * p + 1].first);
}
}
pair<long long, int> queryMaxSegTree(vector<pair<long long, int> > &tree, int l, int r){
int N = tree.size() / 2;
long long total = -1;
int answer = -1;
for (l += N, r += N; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
if (tree[l].second > answer){
answer = tree[l].second;
}
total = (max(total, tree[l++].first));
}
if (r % 2 == 1){
if (tree[r - 1].second > answer){
answer = tree[r - 1].second;
}
total = (max(total, tree[--r].first));
}
}
return make_pair(total, answer);
}
vector<long long> mod_seg_tree;
vector<pair<long long, int> > max_seg_tree;
vector<long long> Xi;
vector<long long> Yi;
set<int> reduced_sequence;
int init(int N, int X[], int Y[]) {
mod_seg_tree = vector<long long> (2 * N, 1);
max_seg_tree = vector<pair<long long, int> > (2 * N, make_pair(0, 0));
for (int i = 0; i < N; i++){
max_seg_tree[i + N].second = i;
}
for (int i = 0; i < N; i++){
Xi.push_back(X[i]);
Yi.push_back(Y[i]);
updateModSegTree(mod_seg_tree, i, X[i]);
updateMaxSegTree(max_seg_tree, i, Y[i]);
}
bool is_current_one = false;
int s_index = 0;
for (int i = 0; i < N; i++){
if (is_current_one){
if (Xi[i] == 1){
} else {
reduced_sequence.insert(s_index);
reduced_sequence.insert(i);
}
} else {
if (Xi[i] == 1){
s_index = i;
is_current_one = true;
} else {
reduced_sequence.insert(i);
}
}
}
if (is_current_one){
reduced_sequence.insert(s_index);
}
long long best = Yi[N - 1];
int b_index = N - 1;
int c_index = N - 1;
long long h_threshold = 1;
set<int>::reverse_iterator it = reduced_sequence.rbegin();
while(h_threshold * best < prime && *(it) != 0){
it++;
int n_index = (*it);
if (Xi[n_index] != 1){
h_threshold *= Xi[n_index + 1];
if (Yi[n_index] > h_threshold){
best = n_index;
b_index = n_index;
}
} else {
pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
if (m.first > h_threshold){
best = m.first;
b_index = m.second;
}
}
c_index = n_index;
}
return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
}
int updateX(int pos, int val) {
int N = mod_seg_tree.size() / 2;
if (Xi[pos] != val){
updateModSegTree(mod_seg_tree, pos, val * mod_exp(val, prime - 1));
if (pos == 0){
if (val == 1){
if (Xi[pos + 1] == 1){
reduced_sequence.erase(pos + 1);
}
}
if (Xi[pos] == 1){
if (Xi[pos + 1] == 1){
reduced_sequence.insert(pos + 1);
}
}
}
if (pos == N - 1){
if (val == 1){
if (Xi[pos - 1] == 1){
reduced_sequence.erase(pos);
}
if (Xi[pos + 1] == 1){
reduced_sequence.erase(pos + 1);
}
}
if (Xi[pos] == 1){
if (Xi[pos + 1] == 1){
reduced_sequence.insert(pos + 1);
}
reduced_sequence.insert(pos);
}
}
Xi[pos] = val;
}
long long best = Yi[N - 1];
int b_index = N - 1;
int c_index = N - 1;
long long h_threshold = 1;
set<int>::reverse_iterator it = reduced_sequence.rbegin();
while(h_threshold * best < prime && *(it) != 0){
it++;
int n_index = (*it);
if (Xi[n_index] != 1){
h_threshold *= Xi[n_index + 1];
if (Yi[n_index] > h_threshold){
best = n_index;
b_index = n_index;
}
} else {
pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
if (m.first > h_threshold){
best = m.first;
b_index = m.second;
}
}
c_index = n_index;
}
return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
}
int updateY(int pos, int val) {
updateMaxSegTree(max_seg_tree, pos, val);
Yi[pos] = val;
long long best = Yi[N - 1];
int b_index = N - 1;
int c_index = N - 1;
long long h_threshold = 1;
set<int>::reverse_iterator it = reduced_sequence.rbegin();
while(h_threshold * best < prime && *(it) != 0){
it++;
int n_index = (*it);
if (Xi[n_index] != 1){
h_threshold *= Xi[n_index + 1];
if (Yi[n_index] > h_threshold){
best = n_index;
b_index = n_index;
}
} else {
pair<long long, int> m = queryMaxSegTree(max_seg_tree, n_index, c_index);
if (m.first > h_threshold){
best = m.first;
b_index = m.second;
}
}
c_index = n_index;
}
return (queryModSegTree(mod_seg_tree, 0, b_index + 1) * Yi[b_index]) % prime;
}