| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 965573 |
2024-04-18T23:12:46 Z |
beaboss |
Horses (IOI15_horses) |
C++17 |
|
536 ms |
62960 KB |
// Source: https://oj.uz/problem/view/IOI15_horses
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
const ll N = 5e5 + 10;
const ll MOD = 1e9 + 7;
#define lc i << 1
#define rc (i << 1) + 1
ll binpow(ll x, ll n) { // x ^ n
ll res = 1;
while (n > 0) {
if (n & 1) res = (res * x) % MOD;
x = (x * x) % MOD;
n/=2;
}
return res;
}
ll st[4 * N];
void up(ll i) {
st[i] = max(st[lc], st[rc]);
}
void update(ll ind, ll val, ll i = 1, ll l = 0, ll r = N) {
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
// cout << l << r << st[i] << endl;
if (r == l) return;
if (r-1 == l && l == ind) {
st[i] = val;
return;
}
if (r-1 == l) return;
ll m = (l + r) / 2;
if (ind < m) update(ind, val, lc, l, m);
if (m <= ind) update(ind, val, rc, m, r);
up(i);
// cout << l << r << ' ' << st[i] << endl;
}
ll query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = N) {
// cout << i << endl;
if (r == l) return 0;
if (ql <= l && r <= qr) {
// cout << ql << qr << ' ' << l << ' ' << r << ' ' << st[i] << endl;
return st[i];
}
if (r == l+1) return 0;
ll m = (l + r) / 2;
ll res = 0;
if (ql <= m) ckmax(res, query(ql, qr, lc, l, m));
if (qr >= m) ckmax(res, query(ql, qr, rc, m, r));
return res;
}
bool cmp(pii a, pii b) {
return (a.f * b.s < b.f * a.s);
}
set<ll> non = {-1};
vi fx, fy;
ll nn;
ll x_prod = 1;
ll solve() {
non.insert(nn-1);
non.insert(0);
ll tot = 1;
pii frac = {0, 1};
auto it = prev(non.end(), 2);
for (; it != non.begin(); it--) {
// cout << *it << endl;
if (tot > MOD) break;
ll rang = query(*it, *next(it, 1)+1);
// cout << (*it) << ' ' << rang << endl;
pii here = {rang, tot};
if (cmp(frac, here)) {
frac=here;
}
tot *= fx[*it];
// ckmax(mul, (binpow(tot, MOD-2) * rang % MOD));
}
// cout << frac.f << ' ' << frac.s << endl;
ll mul = (frac.f * binpow(frac.s, MOD-2) % MOD);
return x_prod * mul % MOD;
}
ll init(int n, int X[], int Y[]) {
nn = n;
non.insert(n + 1);
vi x(n), y(n);
x_prod = 1;
FOR(i, 0, n) {
x[i] = X[i];
y[i] = Y[i];
if (x[i] != 1) non.insert(i);
update(i, y[i]);
x_prod = (x_prod * x[i]) % MOD;
}
fx = x, fy = y;
// cout << query(0, 10) << endl;
// return 0;
return solve();
}
ll updateX(int pos, int val) {
// cout << fx[pos]
x_prod = (x_prod * binpow(fx[pos], MOD-2)) % MOD;
if (fx[pos] != 1) non.erase(pos);
fx[pos]=val;
// cout << x_prod << endl;
if (fx[pos] != 1) non.insert(pos);
x_prod = (x_prod * fx[pos]) % MOD;
return solve();
}
ll updateY(int pos, int val) {
fy[pos]=val;
update(pos, fy[pos]);
return solve();
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << init(10, {10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1}, {10, 10, 2 ,3 ,4, 5, 6, 7, 8, 9}) << endl;
// // cout << updateY(1, 2) << endl;
// // cout << updateX(2, 100) << endl;
// // cout << updateY(2, 200) << endl;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4544 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4548 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 23 |
Correct |
2 ms |
4556 KB |
Output is correct |
| 24 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 25 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 26 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 27 |
Correct |
5 ms |
4444 KB |
Output is correct |
| 28 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 29 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 30 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 31 |
Correct |
4 ms |
4636 KB |
Output is correct |
| 32 |
Correct |
5 ms |
4444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
536 ms |
51648 KB |
Output is correct |
| 2 |
Correct |
305 ms |
51768 KB |
Output is correct |
| 3 |
Correct |
310 ms |
51792 KB |
Output is correct |
| 4 |
Correct |
367 ms |
51776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4576 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 23 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 24 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 25 |
Correct |
2 ms |
4584 KB |
Output is correct |
| 26 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 27 |
Correct |
6 ms |
4624 KB |
Output is correct |
| 28 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 29 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 30 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 31 |
Correct |
4 ms |
4444 KB |
Output is correct |
| 32 |
Correct |
4 ms |
4444 KB |
Output is correct |
| 33 |
Correct |
86 ms |
32296 KB |
Output is correct |
| 34 |
Correct |
82 ms |
32140 KB |
Output is correct |
| 35 |
Correct |
203 ms |
62664 KB |
Output is correct |
| 36 |
Correct |
194 ms |
62960 KB |
Output is correct |
| 37 |
Correct |
119 ms |
30288 KB |
Output is correct |
| 38 |
Correct |
142 ms |
43088 KB |
Output is correct |
| 39 |
Correct |
78 ms |
30284 KB |
Output is correct |
| 40 |
Correct |
178 ms |
57668 KB |
Output is correct |
| 41 |
Correct |
92 ms |
30240 KB |
Output is correct |
| 42 |
Correct |
124 ms |
30452 KB |
Output is correct |
| 43 |
Correct |
179 ms |
58292 KB |
Output is correct |
| 44 |
Correct |
172 ms |
58020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4548 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 23 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 24 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 25 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 26 |
Correct |
2 ms |
4572 KB |
Output is correct |
| 27 |
Correct |
5 ms |
4632 KB |
Output is correct |
| 28 |
Correct |
3 ms |
4556 KB |
Output is correct |
| 29 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 30 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 31 |
Correct |
3 ms |
4556 KB |
Output is correct |
| 32 |
Correct |
5 ms |
4444 KB |
Output is correct |
| 33 |
Correct |
495 ms |
53928 KB |
Output is correct |
| 34 |
Correct |
346 ms |
62864 KB |
Output is correct |
| 35 |
Correct |
316 ms |
54000 KB |
Output is correct |
| 36 |
Correct |
346 ms |
57792 KB |
Output is correct |
| 37 |
Correct |
84 ms |
32096 KB |
Output is correct |
| 38 |
Correct |
96 ms |
32316 KB |
Output is correct |
| 39 |
Correct |
194 ms |
62656 KB |
Output is correct |
| 40 |
Correct |
194 ms |
62828 KB |
Output is correct |
| 41 |
Correct |
119 ms |
30348 KB |
Output is correct |
| 42 |
Correct |
141 ms |
42908 KB |
Output is correct |
| 43 |
Correct |
77 ms |
30244 KB |
Output is correct |
| 44 |
Correct |
181 ms |
57708 KB |
Output is correct |
| 45 |
Correct |
90 ms |
30292 KB |
Output is correct |
| 46 |
Correct |
102 ms |
30244 KB |
Output is correct |
| 47 |
Correct |
170 ms |
58196 KB |
Output is correct |
| 48 |
Correct |
171 ms |
58192 KB |
Output is correct |
| 49 |
Correct |
181 ms |
32340 KB |
Output is correct |
| 50 |
Correct |
159 ms |
32168 KB |
Output is correct |
| 51 |
Correct |
315 ms |
62804 KB |
Output is correct |
| 52 |
Correct |
266 ms |
62800 KB |
Output is correct |
| 53 |
Correct |
508 ms |
30388 KB |
Output is correct |
| 54 |
Correct |
284 ms |
43092 KB |
Output is correct |
| 55 |
Correct |
170 ms |
30548 KB |
Output is correct |
| 56 |
Correct |
276 ms |
57680 KB |
Output is correct |
| 57 |
Correct |
308 ms |
30548 KB |
Output is correct |
| 58 |
Correct |
415 ms |
30548 KB |
Output is correct |
| 59 |
Correct |
186 ms |
58128 KB |
Output is correct |
