| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 586444 | tranxuanbach | 말 (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.
#ifndef FEXT
#include "horses.h"
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
template<class T, class F>
struct segment_tree{
int n, size, log;
vector<T> data;
F TT; // monoid operation (always adjacent)
T T_id; // monoid identity
// O(n)
segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
// O(n)
segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
// O(n)
segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
log = __lg(max(n - 1, 1)) + 1, size = 1 << log;
data = vector<T>(size << 1, T_id);
copy(a.begin(), a.end(), data.begin() + size);
for(auto i = size - 1; i >= 1; -- i) refresh(i);
}
// O(1)
void refresh(int i){
data[i] = TT(data[i << 1], data[i << 1 | 1]);
}
// O(log n)
void set(int p, T x){
assert(0 <= p && p < n);
data[p += size] = x;
for(auto i = 1; i <= log; ++ i) refresh(p >> i);
}
// O(1)
T query(int p) const{
assert(0 <= p && p < n);
return data[p + size];
}
// O(log n)
T query(int l, int r) const{
assert(0 <= l && l <= r && r <= n);
T res_left = T_id, res_right = T_id;
for(l += size, r += size; l < r; l >>= 1, r >>= 1){
if(l & 1) res_left = TT(res_left, data[l ++]);
if(r & 1) res_right = TT(data[-- r], res_right);
}
return TT(res_left, res_right);
}
// O(1)
T query_all() const{
return data[1];
}
// pred(sum[l, r)) is T, T, ..., T, F, F, ..., F
// Returns max r with T
// O(log n)
int max_pref(int l, auto pred) const{
assert(0 <= l && l <= n && pred(T_id));
if(l == n) return n;
l += size;
T sm = T_id;
do{
while(~l & 1) l >>= 1;
if(!pred(TT(sm, data[l]))){
while(l < size){
l = l << 1;
if(pred(TT(sm, data[l]))) sm = TT(sm, data[l ++]);
}
return l - size;
}
sm = TT(sm, data[l ++]);
}while((l & -l) != l);
return n;
}
// pred(sum[l, r)) is F, F, ..., F, T, T, ..., T
// Returns min l with T
// O(log n)
int min_suff(int r, auto pred) const{
assert(0 <= r && r <= n && pred(T_id));
if(r == 0) return 0;
r += size;
T sm = T_id;
do{
-- r;
while(r > 1 && r & 1) r >>= 1;
if(!pred(TT(data[r], sm))){
while(r < size){
r = r << 1 | 1;
if(pred(TT(data[r], sm))) sm = TT(data[r --], sm);
}
return r + 1 - size;
}
sm = TT(data[r], sm);
}while((r & -r) != r);
return 0;
}
template<class output_stream>
friend output_stream &operator<<(output_stream &out, const segment_tree<T, F> &seg){
out << "[";
for(auto i = 0; i < seg.n; ++ i){
out << seg.query(i);
if(i != seg.n - 1) out << ", ";
}
return out << ']';
}
};
const int N = 5e5 + 5, inf = 1e9 + 7, mod = 1e9 + 7;
struct Tmax{
int mx;
Tmax(int mx = numeric_limits <int>::min()): mx(mx){
}
};
auto TTmax = [](const Tmax &lhs, const Tmax &rhs){
return Tmax(max(lhs.mx, rhs.mx));
};
struct Tprod{
int prod;
Tprod(int prod = 1): prod(prod){
}
};
auto TTprod = [](const Tprod &lhs, const Tprod &rhs){
return Tprod((ll)lhs.prod * rhs.prod % mod);
};
int n;
int x[N], y[N];
set <int> stt;
segment_tree <Tprod, decltype(TTprod)> segx(N, TTprod, Tprod());
segment_tree <Tmax, decltype(TTmax)> segy(N, TTmax, Tmax());
int real_solve(){
auto itr = prev(stt.end());
int prod = 1;
while (itr != stt.begin() and (ll)prod * x[(*itr)] < inf){
prod *= x[*itr];
itr = prev(itr);
}
int ans = segx.query(0, *itr + 1).prod;
prod = 1; ll mxprod = 0;
while (itr != stt.end()){
int l = max(0, *itr), r = (next(itr) == stt.end() ? n : *next(itr));
mxprod = max(mxprod, (ll)prod * segy.query(l, r).mx);
if (next(itr) != stt.end()){
prod *= x[*next(itr)];
}
itr = next(itr);
}
mxprod %= mod;
ans = (ll)ans * mxprod % mod;
return ans;
}
int init(int _n, int _x[], int _y[]){
n = _n;
For(i, 0, n){
x[i] = _x[i];
y[i] = _y[i];
}
stt.emplace(-1);
For(i, 0, n){
if (x[i] != 1){
stt.emplace(i);
}
}
For(i, 0, n){
segx.set(i, Tprod(x[i]));
segy.set(i, Tmax(y[i]));
}
return real_solve();
}
int updateX(int pos, int val){
if (x[pos] != 1 and val == 1){
stt.erase(pos);
}
if (x[pos] == 1 and val != 1){
stt.emplace(pos);
}
segx.set(pos, Tprod(val));
x[pos] = val;
return real_solve();
}
int updateY(int pos, int val){
segy.set(pos, Tmax(val));
y[pos] = val;
return real_solve();
}
#ifdef FEXT
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
_inputFile = fopen("KEK.inp", "rb");
_outputFile = fopen("KEK.out", "w");
int N; N = _readInt();
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
X[i] = _readInt();
}
for (int i = 0; i < N; i++) {
Y[i] = _readInt();
}
fprintf(_outputFile,"%d\n",init(N,X,Y));
int M; M = _readInt();
for (int i = 0; i < M; i++) {
int type; type = _readInt();
int pos; pos = _readInt();
int val; val = _readInt();
if (type == 1) {
fprintf(_outputFile,"%d\n",updateX(pos,val));
} else if (type == 2) {
fprintf(_outputFile,"%d\n",updateY(pos,val));
}
}
return 0;
}
#endif
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/