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 <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
vector<int> x, y;
int n;
struct segtree1 {
vector<double> st, lz;
vector<int> id;
int sz;
void init(const vector<double> &a) {
sz = a.size();
while (sz & sz - 1) ++sz;
st.resize(sz << 1), lz.resize(sz << 1), id.resize(sz << 1);
for (int i = 0; i < a.size(); i++) st[i + sz] = a[i] + log2(y[i]), id[i + sz] = i;
for (int i = sz - 1; i; i--) pull(i);
}
void pull(int v) {
if (st[v << 1] >= st[v << 1 | 1]) st[v] = st[v << 1], id[v] = id[v << 1];
else st[v] = st[v << 1 | 1], id[v] = id[v << 1 | 1];
}
void push(int v) {
st[v << 1] += lz[v];
st[v << 1 | 1] += lz[v];
lz[v << 1] += lz[v];
lz[v << 1 | 1] += lz[v];
lz[v] = 0;
}
void updx(int v, int l, int r, int ql, int qr, double x) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
st[v] += x, lz[v] += x;
return;
}
if (lz[v] != 0) push(v);
int m = l + r >> 1;
updx(v << 1, l, m, ql, qr, x);
updx(v << 1 | 1, m + 1, r, ql, qr, x);
pull(v);
}
void updy(int v, int l, int r, int u, double y) {
if (l == r) {
st[v] += y;
return;
}
if (lz[v] != 0) push(v);
int m = l + r >> 1;
if (u <= m) updy(v << 1, l, m, u, y);
else updy(v << 1 | 1, m + 1, r, u, y);
pull(v);
}
void updx(int l, int r, double x) {
updx(1, 0, sz - 1, l, r, x);
}
void updy(int u, double y) {
updy(1, 0, sz - 1, u, y);
}
} st1;
struct segtree2 {
vector<int> st;
int sz;
void init(int n) {
sz = n;
st.resize(sz << 1);
}
void upd(int id, int x) {
for (st[id += sz] = x; id >>= 1;) st[id] = 1LL * st[id << 1] * st[id << 1 | 1] % mod;
}
int qry(int l, int r) {
int s = 1;
for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) s = 1LL * s * st[l++] % mod;
if (r & 1) s = 1LL * s * st[--r] % mod;
}
return s;
}
} st2;
int init(int N, int X[], int Y[]) {
n = N, x.resize(n), y.resize(n);
for (int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i];
vector<double> p(n);
p[0] = log2(x[0]);
for (int i = 1; i < n; i++) p[i] = p[i - 1] + log2(x[i]);
st1.init(p), st2.init(n);
for (int i = 0; i < n; i++) st2.upd(i, x[i]);
return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
}
int updateX(int pos, int val) {
st1.updx(pos, n - 1, log2(val) - log2(x[pos]));
st2.upd(pos, val);
x[pos] = val;
return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
}
int updateY(int pos, int val) {
st1.updy(pos, log2(val) - log2(y[pos]));
y[pos] = val;
return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
}
Compilation message (stderr)
horses.cpp: In member function 'void segtree1::init(const std::vector<double>&)':
horses.cpp:14:20: warning: conversion from 'std::vector<double>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
14 | sz = a.size();
| ~~~~~~^~
horses.cpp:15:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | while (sz & sz - 1) ++sz;
| ~~~^~~
horses.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int i = 0; i < a.size(); i++) st[i + sz] = a[i] + log2(y[i]), id[i + sz] = i;
| ~~^~~~~~~~~~
horses.cpp: In member function 'void segtree1::updx(int, int, int, int, int, double)':
horses.cpp:31:59: warning: declaration of 'x' shadows a global declaration [-Wshadow]
31 | void updx(int v, int l, int r, int ql, int qr, double x) {
| ~~~~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In member function 'void segtree1::updy(int, int, int, int, double)':
horses.cpp:43:50: warning: declaration of 'y' shadows a global declaration [-Wshadow]
43 | void updy(int v, int l, int r, int u, double y) {
| ~~~~~~~^
horses.cpp:6:16: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In member function 'void segtree1::updx(int, int, double)':
horses.cpp:54:36: warning: declaration of 'x' shadows a global declaration [-Wshadow]
54 | void updx(int l, int r, double x) {
| ~~~~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'void segtree1::updy(int, double)':
horses.cpp:57:29: warning: declaration of 'y' shadows a global declaration [-Wshadow]
57 | void updy(int u, double y) {
| ~~~~~~~^
horses.cpp:6:16: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp: In member function 'void segtree2::init(int)':
horses.cpp:65:19: warning: declaration of 'n' shadows a global declaration [-Wshadow]
65 | void init(int n) {
| ~~~~^
horses.cpp:7:5: note: shadowed declaration is here
7 | int n;
| ^
horses.cpp: In member function 'void segtree2::upd(int, int)':
horses.cpp:69:26: warning: declaration of 'x' shadows a global declaration [-Wshadow]
69 | void upd(int id, int x) {
| ~~~~^
horses.cpp:6:13: note: shadowed declaration is here
6 | vector<int> x, y;
| ^
horses.cpp:70:88: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
70 | for (st[id += sz] = x; id >>= 1;) st[id] = 1LL * st[id << 1] * st[id << 1 | 1] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int segtree2::qry(int, int)':
horses.cpp:75:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
75 | if (l & 1) s = 1LL * s * st[l++] % mod;
| ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:76:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
76 | if (r & 1) s = 1LL * s * st[--r] % mod;
| ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:97:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
97 | return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
103 | return 1LL * st2.qry(0, st1.id[1]) * y[st1.id[1]] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |