| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 599082 |
2022-07-19T09:56:18 Z |
Temmie |
Horses (IOI15_horses) |
C++17 |
|
1500 ms |
35732 KB |
#include <bits/stdc++.h>
struct Seg_max {
int size;
std::vector <int> v;
Seg_max(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
v.resize(size << 1, 0);
}
void update(int ind, int val) {
update(ind, val, 0, 0, size);
}
void update(int ind, int val, int now, int l, int r) {
if (!(r - l - 1)) {
v[now] = val;
return;
}
int mid = (l + r) >> 1;
if (ind < mid) {
update(ind, val, now * 2 + 1, l, mid);
} else {
update(ind, val, now * 2 + 2, mid, r);
}
v[now] = std::max(v[now * 2 + 1], v[now * 2 + 2]);
}
int query(int l, int r) {
return query(l, r, 0, 0, size);
}
int query(int tl, int tr, int now, int l, int r) {
if (l >= tr || r <= tl) {
return 0;
}
if (l >= tl && r <= tr) {
return v[now];
}
int mid = (l + r) >> 1;
return std::max(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
}
};
constexpr const int mod = 1e9 + 7;
int pw(int x, int p) {
int res = 1;
while (p) {
if (p & 1) {
res = (long long) res * x % mod;
}
p >>= 1;
x = (long long) x * x % mod;
}
return res;
}
int inv(int val) {
return pw(val, mod - 2);
}
int dv(int nu, int de) {
nu %= mod;
de %= mod;
return (long long) nu * inv(de);
}
int n;
std::vector <int> gr, pr;
Seg_max seg_max(0);
std::set <int> st;
int tot_gr;
int get() {
st.insert(0);
for (int i = 0; i < n; i++) st.insert(i); // temp
long long gr_div = 1;
int res = (long long) tot_gr * pr[n - 1] % mod;
for (auto it = st.rbegin(); it != st.rend(); it++) {
int ind = *it;
int sfmx = seg_max.query(ind, n);
if (sfmx >= gr_div || res <= (long long) dv(tot_gr, gr_div) * sfmx % mod) {
res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
}
gr_div *= gr[ind];
if (gr_div > (1LL << 30)) {
break;
}
}
return res;
}
int init(int _n, int _gr[], int _pr[]) {
n = _n;
gr.resize(n);
pr.resize(n);
seg_max = Seg_max(n);
tot_gr = 1;
for (int i = 0; i < n; i++) {
gr[i] = _gr[i];
pr[i] = _pr[i];
if (gr[i] > 1) st.insert(i);
seg_max.update(i, pr[i]);
tot_gr = (long long) tot_gr * gr[i] % mod;
}
return get();
}
// gr
int updateX(int pos, int val) {
tot_gr = dv(tot_gr, gr[pos]);
tot_gr = (long long) tot_gr * (gr[pos] = val) % mod;
st.erase(pos);
if (gr[pos] > 1) st.insert(pos);
return get();
}
// pr
int updateY(int pos, int val) {
seg_max.update(pos, pr[pos] = val);
return get();
}
Compilation message
horses.cpp: In function 'int pw(int, int)':
horses.cpp:57:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
57 | res = (long long) res * x % mod;
| ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:60:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
60 | x = (long long) x * x % mod;
| ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:86:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
86 | int res = (long long) tot_gr * pr[n - 1] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:90:55: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | if (sfmx >= gr_div || res <= (long long) dv(tot_gr, gr_div) * sfmx % mod) {
| ^~~~~~
horses.cpp:91:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
91 | res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
| ^~~~~~
horses.cpp:91:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
91 | res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:112:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
112 | tot_gr = (long long) tot_gr * gr[i] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
120 | tot_gr = (long long) tot_gr * (gr[pos] = val) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1558 ms |
35732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
304 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
