# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
785172 |
2023-07-17T06:47:57 Z |
Sohsoh84 |
Horses (IOI15_horses) |
C++17 |
|
448 ms |
44784 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define X first
#define Y second
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXN = 3e6 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
const ll LOG = 30;
inline ll poww(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
inline bool cmp(pll a, pll b) {
return a.X * b.Y > a.Y * b.X;
}
ll X[MAXN], Y[MAXN], n;
namespace segment {
ll sg[MAXN];
void build(int l = 1, int r = n, int v = 1) {
if (l == r) sg[v] = Y[l];
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
void update(int ind, int l = 1, int r = n, int v = 1) {
if (l == r) sg[v] = Y[l];
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(ind, l, mid, v << 1);
else update(ind, mid + 1, r, v << 1 | 1);
sg[v] = max(sg[v << 1], sg[v << 1 | 1]);
}
}
ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sg[v];
int mid = (l + r) >> 1;
return max(query(ql, qr, l, mid, v << 1),
query(ql, qr, mid + 1, r, v << 1 | 1));
}
}
set<int> st;
ll mul = 1;
inline ll solve() {
ll f = 1;
pll best = {Y[n], 1};
int j = 0;
for (auto it = prev(prev(st.end())); j < LOG && f < INF; it--, j++) {
int nxt = *next(it);
int i = *it;
ll mx = segment::query(i, nxt - 1);
if (cmp(pll(mx, f), best)) best = pll(mx, f);
f *= X[i];
if (it == st.begin()) break;
}
return mul * best.X % MOD * poww(best.Y, MOD - 2) % MOD;
}
int init(int N_, int X_[], int Y_[]) {
n = N_;
for (int i = 1; i <= n; i++) {
X[i] = X_[i - 1], Y[i] = Y_[i - 1];
if (X[i] > 1) st.insert(i);
mul = mul * X[i] % MOD;
}
segment::build();
st.insert(1);
st.insert(n + 1);
return solve();
}
int updateX(int pos, int val) {
pos++;
mul = mul * poww(X[pos], MOD - 2) % MOD;
if (pos > 1) {
if (X[pos] > 1 && val == 1) st.erase(pos);
else if (X[pos] == 1 && val > 1) st.insert(pos);
}
X[pos] = val;
mul = mul * X[pos] % MOD;
return solve();
}
int updateY(int pos, int val) {
pos++;
Y[pos] = val;
segment::update(pos);
return solve();
}
Compilation message
horses.cpp:38:44: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
38 | void build(int l = 1, int r = n, int v = 1) {
| ^
horses.cpp:48:54: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
48 | void update(int ind, int l = 1, int r = n, int v = 1) {
| ^
horses.cpp:59:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
59 | ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
| ^
horses.cpp: In function 'll solve()':
horses.cpp:81:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
81 | ll mx = segment::query(i, nxt - 1);
| ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
99 | segment::build();
| ^
horses.cpp:101:14: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
101 | st.insert(n + 1);
| ~~^~~
horses.cpp:102:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
102 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:116:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
116 | return solve();
| ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
122 | segment::update(pos);
| ^
horses.cpp:123:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
123 | return solve();
| ~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
224 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
284 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
416 KB |
Output is correct |
31 |
Correct |
2 ms |
340 KB |
Output is correct |
32 |
Correct |
3 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
448 ms |
44672 KB |
Output is correct |
2 |
Correct |
238 ms |
44728 KB |
Output is correct |
3 |
Correct |
209 ms |
44688 KB |
Output is correct |
4 |
Correct |
254 ms |
44656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
340 KB |
Output is correct |
32 |
Correct |
3 ms |
340 KB |
Output is correct |
33 |
Correct |
44 ms |
20496 KB |
Output is correct |
34 |
Correct |
39 ms |
20456 KB |
Output is correct |
35 |
Correct |
161 ms |
43860 KB |
Output is correct |
36 |
Correct |
152 ms |
43812 KB |
Output is correct |
37 |
Correct |
74 ms |
20388 KB |
Output is correct |
38 |
Correct |
81 ms |
32232 KB |
Output is correct |
39 |
Correct |
31 ms |
20172 KB |
Output is correct |
40 |
Correct |
139 ms |
43820 KB |
Output is correct |
41 |
Correct |
46 ms |
20372 KB |
Output is correct |
42 |
Correct |
57 ms |
20332 KB |
Output is correct |
43 |
Correct |
129 ms |
43652 KB |
Output is correct |
44 |
Correct |
129 ms |
43660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
3 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
340 KB |
Output is correct |
32 |
Correct |
3 ms |
340 KB |
Output is correct |
33 |
Correct |
447 ms |
44632 KB |
Output is correct |
34 |
Correct |
222 ms |
44656 KB |
Output is correct |
35 |
Correct |
205 ms |
44648 KB |
Output is correct |
36 |
Correct |
223 ms |
44784 KB |
Output is correct |
37 |
Correct |
40 ms |
20400 KB |
Output is correct |
38 |
Correct |
39 ms |
20460 KB |
Output is correct |
39 |
Correct |
156 ms |
43848 KB |
Output is correct |
40 |
Correct |
153 ms |
43964 KB |
Output is correct |
41 |
Correct |
80 ms |
20476 KB |
Output is correct |
42 |
Correct |
82 ms |
32212 KB |
Output is correct |
43 |
Correct |
29 ms |
20172 KB |
Output is correct |
44 |
Correct |
135 ms |
43760 KB |
Output is correct |
45 |
Correct |
56 ms |
20320 KB |
Output is correct |
46 |
Correct |
58 ms |
20340 KB |
Output is correct |
47 |
Correct |
129 ms |
43692 KB |
Output is correct |
48 |
Correct |
128 ms |
43708 KB |
Output is correct |
49 |
Correct |
119 ms |
22368 KB |
Output is correct |
50 |
Correct |
107 ms |
22476 KB |
Output is correct |
51 |
Correct |
260 ms |
44744 KB |
Output is correct |
52 |
Correct |
200 ms |
44676 KB |
Output is correct |
53 |
Correct |
445 ms |
22220 KB |
Output is correct |
54 |
Correct |
203 ms |
35212 KB |
Output is correct |
55 |
Correct |
102 ms |
20476 KB |
Output is correct |
56 |
Correct |
234 ms |
44676 KB |
Output is correct |
57 |
Correct |
264 ms |
21216 KB |
Output is correct |
58 |
Correct |
375 ms |
21212 KB |
Output is correct |
59 |
Correct |
136 ms |
43760 KB |
Output is correct |