# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1018578 | 2024-07-10T07:03:31 Z | AmirAli_H1 | Horses (IOI15_horses) | C++17 | 905 ms | 37800 KB |
// In the name of Allah #include <bits/stdc++.h> #include "horses.h" using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct node { ll mul, mx; int ind; }; const int maxn = (1 << 19) + 4; const int maxlg = 20; const int mod = 1e9 + 7; int n; pll A[maxn]; node t[2 * maxn], ca; node f(node a, node b) { node res; res.mul = a.mul * b.mul % mod; res.mx = max(a.mx, b.mx); res.ind = max(a.ind, b.ind); return res; } pll fx(pll a, pll b) { return Mp(max(a.F, b.F), max(a.S, b.S)); } void build(int v, int tl, int tr) { if (tr - tl == 1) { t[v].mul = A[tl].F; t[v].mx = A[tl].S; if (A[tl].F == 1) t[v].ind = -1; else t[v].ind = tl; return ; } int mid = (tl + tr) / 2; build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr); t[v] = f(t[2 * v + 1], t[2 * v + 2]); } void upd(int v, int tl, int tr, int i) { if (i >= tr || i < tl) return ; if (tr - tl == 1) { t[v].mul = A[tl].F; t[v].mx = A[tl].S; if (A[tl].F == 1) t[v].ind = -1; else t[v].ind = tl; return ; } int mid = (tl + tr) / 2; upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i); t[v] = f(t[2 * v + 1], t[2 * v + 2]); } pll get_res(int v, int tl, int tr, int l, int r) { l = max(l, tl); r = min(r, tr); if (l >= tr || r <= tl) return Mp(ca.mx, ca.ind); if (l == tl && r == tr) return Mp(t[v].mx, t[v].ind); int mid = (tl + tr) / 2; return fx(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r)); } ll get_mul(int v, int tl, int tr, int l, int r) { l = max(l, tl); r = min(r, tr); if (l >= tr || r <= tl) return ca.mul; if (l == tl && r == tr) return t[v].mul; int mid = (tl + tr) / 2; return get_mul(2 * v + 1, tl, mid, l, r) * get_mul(2 * v + 2, mid, tr, l, r) % mod; } ll get_ans() { ll mx = 1; int j = n; while (j > 0) { pll res = get_res(0, 0, n, 0, j); int k = res.S; if (k == -1) { mx = max(mx, res.F); j = 0; } else { res = get_res(0, 0, n, k, j); mx = max(mx, res.F) * A[k].F; j = k; if (mx >= mod) break; } } return (mx % mod) * get_mul(0, 0, n, 0, j) % mod; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++) A[i] = Mp(X[i], Y[i]); ca.mul = 1; ca.mx = 0; ca.ind = -1; build(0, 0, n); return get_ans(); } int updateX(int i, int val) { A[i].F = val; upd(0, 0, n, i); return get_ans(); } int updateY(int i, int val) { A[i].S = val; upd(0, 0, n, i); return get_ans(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 0 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2392 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 1 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2648 KB | Output is correct |
13 | Correct | 0 ms | 2396 KB | Output is correct |
14 | Correct | 0 ms | 2396 KB | Output is correct |
15 | Correct | 0 ms | 2392 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2392 KB | Output is correct |
20 | Correct | 0 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 0 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 1 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2440 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 0 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2568 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 2 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2396 KB | Output is correct |
27 | Correct | 5 ms | 2392 KB | Output is correct |
28 | Correct | 2 ms | 2396 KB | Output is correct |
29 | Correct | 1 ms | 2396 KB | Output is correct |
30 | Correct | 1 ms | 2396 KB | Output is correct |
31 | Correct | 4 ms | 2392 KB | Output is correct |
32 | Correct | 4 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 786 ms | 37716 KB | Output is correct |
2 | Correct | 128 ms | 37712 KB | Output is correct |
3 | Correct | 198 ms | 37712 KB | Output is correct |
4 | Correct | 115 ms | 37716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 0 ms | 2648 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2496 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 0 ms | 2392 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 1 ms | 2408 KB | Output is correct |
19 | Correct | 0 ms | 2496 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2396 KB | Output is correct |
27 | Correct | 6 ms | 2556 KB | Output is correct |
28 | Correct | 2 ms | 2396 KB | Output is correct |
29 | Correct | 1 ms | 2396 KB | Output is correct |
30 | Correct | 1 ms | 2568 KB | Output is correct |
31 | Correct | 3 ms | 2396 KB | Output is correct |
32 | Correct | 4 ms | 2396 KB | Output is correct |
33 | Correct | 32 ms | 36764 KB | Output is correct |
34 | Correct | 38 ms | 36700 KB | Output is correct |
35 | Correct | 68 ms | 36852 KB | Output is correct |
36 | Correct | 53 ms | 36692 KB | Output is correct |
37 | Correct | 119 ms | 37084 KB | Output is correct |
38 | Correct | 40 ms | 36892 KB | Output is correct |
39 | Correct | 27 ms | 36700 KB | Output is correct |
40 | Correct | 43 ms | 36696 KB | Output is correct |
41 | Correct | 71 ms | 36696 KB | Output is correct |
42 | Correct | 98 ms | 36976 KB | Output is correct |
43 | Correct | 33 ms | 36760 KB | Output is correct |
44 | Correct | 34 ms | 36724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 1 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2396 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 0 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 1 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 0 ms | 2392 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2560 KB | Output is correct |
27 | Correct | 4 ms | 2564 KB | Output is correct |
28 | Correct | 2 ms | 2396 KB | Output is correct |
29 | Correct | 1 ms | 2396 KB | Output is correct |
30 | Correct | 1 ms | 2648 KB | Output is correct |
31 | Correct | 4 ms | 2396 KB | Output is correct |
32 | Correct | 4 ms | 2564 KB | Output is correct |
33 | Correct | 728 ms | 37736 KB | Output is correct |
34 | Correct | 130 ms | 37724 KB | Output is correct |
35 | Correct | 192 ms | 37632 KB | Output is correct |
36 | Correct | 120 ms | 37720 KB | Output is correct |
37 | Correct | 35 ms | 36860 KB | Output is correct |
38 | Correct | 34 ms | 36700 KB | Output is correct |
39 | Correct | 67 ms | 36880 KB | Output is correct |
40 | Correct | 54 ms | 36900 KB | Output is correct |
41 | Correct | 135 ms | 36732 KB | Output is correct |
42 | Correct | 41 ms | 36700 KB | Output is correct |
43 | Correct | 40 ms | 36700 KB | Output is correct |
44 | Correct | 40 ms | 36696 KB | Output is correct |
45 | Correct | 74 ms | 36696 KB | Output is correct |
46 | Correct | 118 ms | 36904 KB | Output is correct |
47 | Correct | 36 ms | 36672 KB | Output is correct |
48 | Correct | 32 ms | 36584 KB | Output is correct |
49 | Correct | 139 ms | 37716 KB | Output is correct |
50 | Correct | 112 ms | 37656 KB | Output is correct |
51 | Correct | 256 ms | 37800 KB | Output is correct |
52 | Correct | 104 ms | 37712 KB | Output is correct |
53 | Correct | 905 ms | 37712 KB | Output is correct |
54 | Correct | 217 ms | 37676 KB | Output is correct |
55 | Correct | 129 ms | 36944 KB | Output is correct |
56 | Correct | 117 ms | 37712 KB | Output is correct |
57 | Correct | 534 ms | 37712 KB | Output is correct |
58 | Correct | 834 ms | 37660 KB | Output is correct |
59 | Correct | 31 ms | 36696 KB | Output is correct |