| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 964464 |
2024-04-17T00:24:54 Z |
beaboss |
Horses (IOI15_horses) |
C++14 |
|
318 ms |
51232 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;
}
struct node {
ll val, lz;
} st[4 * N];
void down(ll i) {
if (st[i].lz == 1) return;
st[lc].lz = st[lc].lz * st[i].lz % MOD;
st[rc].lz = st[rc].lz * st[i].lz %MOD;
st[lc].val = st[lc].val * st[i].lz % MOD;
st[rc].val = st[rc].val * st[i].lz % MOD;
st[i].lz = 1;
}
void up(ll i) {
st[i].val = max(st[lc].val, st[rc].val);
}
void update(ll ul, ll ur, ll val, ll i = 1, ll l = 0, ll r = N) {
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
if (r == l) return;
if (ul <= l && r <= ur) {
st[i].lz = (st[i].lz*val) % MOD;
st[i].val = (st[i].val * val) % MOD;
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
return;
}
if (l == r-1) return;
down(i);
ll m = (l + r) / 2;
if (ul < m) update(ul, ur, val, lc, l, m);
if (m < ur) update(ul, ur, val, rc, m, r);
up(i);
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
}
vi fx, fy;
ll nn;
ll init(int n, int X[], int Y[]) {
nn = n;
vi x(n), y(n);
FOR(i, 0, n) {
x[i] = X[i];
y[i] = Y[i];
}
fx = x, fy = y;
FOR(i, 0, 4 * N) {
st[i].val = st[i].lz = 1;
}
FOR(i, 0, n) {
update(i, n, x[i]);
// break;
update(i, i + 1, y[i]);
// break;
}
return st[1].val;
}
ll updateX(int pos, int val) {
update(pos, nn, binpow(fx[pos], MOD-2));
fx[pos]=val;
update(pos, nn, fx[pos]);
return st[1].val;
}
ll updateY(int pos, int val) {
update(pos, pos + 1, binpow(fy[pos], MOD-2));
fy[pos]=val;
update(pos, pos, fy[pos]);
return st[1].val;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << init(3, {2, 1, 3}, {3, 4, 1}) << endl;
// cout << updateY(1, 2) << endl;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
31576 KB |
Output is correct |
| 2 |
Correct |
6 ms |
31628 KB |
Output is correct |
| 3 |
Correct |
8 ms |
31832 KB |
Output is correct |
| 4 |
Correct |
5 ms |
31584 KB |
Output is correct |
| 5 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 6 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 7 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 8 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 9 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 10 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 11 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 12 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 13 |
Correct |
6 ms |
31836 KB |
Output is correct |
| 14 |
Correct |
6 ms |
31620 KB |
Output is correct |
| 15 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 16 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 17 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 18 |
Correct |
5 ms |
31596 KB |
Output is correct |
| 19 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 20 |
Correct |
5 ms |
31744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
31612 KB |
Output is correct |
| 2 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 3 |
Correct |
5 ms |
31660 KB |
Output is correct |
| 4 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 5 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 6 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 7 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 8 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 9 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 10 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 11 |
Correct |
5 ms |
31612 KB |
Output is correct |
| 12 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 13 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 14 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 15 |
Correct |
5 ms |
31748 KB |
Output is correct |
| 16 |
Correct |
5 ms |
31632 KB |
Output is correct |
| 17 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 18 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 19 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 20 |
Correct |
6 ms |
31584 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
31604 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
318 ms |
51232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 2 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 4 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 5 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 6 |
Correct |
6 ms |
31600 KB |
Output is correct |
| 7 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 8 |
Correct |
7 ms |
31580 KB |
Output is correct |
| 9 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 10 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 11 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 12 |
Correct |
5 ms |
31612 KB |
Output is correct |
| 13 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 14 |
Correct |
5 ms |
31632 KB |
Output is correct |
| 15 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 16 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 17 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 18 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 19 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 20 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
31596 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
31604 KB |
Output is correct |
| 3 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 5 |
Correct |
6 ms |
31636 KB |
Output is correct |
| 6 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 7 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 8 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 9 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 10 |
Correct |
5 ms |
31624 KB |
Output is correct |
| 11 |
Correct |
5 ms |
31832 KB |
Output is correct |
| 12 |
Correct |
4 ms |
31576 KB |
Output is correct |
| 13 |
Correct |
5 ms |
31616 KB |
Output is correct |
| 14 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 15 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 16 |
Correct |
6 ms |
31832 KB |
Output is correct |
| 17 |
Correct |
5 ms |
31592 KB |
Output is correct |
| 18 |
Correct |
5 ms |
31632 KB |
Output is correct |
| 19 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 20 |
Correct |
5 ms |
31588 KB |
Output is correct |
| 21 |
Incorrect |
5 ms |
31584 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
