| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846810 |
2023-09-08T13:27:23 Z |
12345678 |
Horses (IOI15_horses) |
C++17 |
|
296 ms |
75148 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=5e5+5, mod=1e9+7, mx=(ll)INT_MAX+1;
int n;
vector<ll> x(nx), y(nx);
struct segtree
{
struct node
{
ll pre, suf, sm, ans, p, sx;
} d[4*nx];
ll a[nx], b[nx];
void update(int l, int r, int i, int idx, ll vx, ll vy)
{
if (r<idx||idx<l) return;
if (l==r)
{
d[i].ans=(vx*vy)%mod;
d[i].pre=d[i].sm=vx;
d[i].suf=1; d[i].p=vy; d[i].sx=vx;
return;
}
int md=(l+r)/2;
update(l, md, 2*i, idx, vx, vy);
update(md+1, r, 2*i+1, idx, vx, vy);
d[i].sx=(d[2*i].sx*d[2*i+1].sx)%mod;
if (d[2*i].p<min(d[2*i].suf*d[2*i+1].pre, mx)*d[2*i+1].p)
{
d[i].ans=(d[2*i].sx*d[2*i+1].ans)%mod;
d[i].pre=min(d[2*i].sm*d[2*i+1].pre, mx);
d[i].sm=min(d[2*i].sm*d[2*i+1].sm, mx);
d[i].suf=d[2*i+1].suf;
d[i].p=d[2*i+1].p;
}
else
{
d[i].ans=d[2*i].ans;
d[i].pre=d[2*i].pre;
d[i].sm=min(d[2*i].sm*d[2*i+1].sm, mx);
d[i].suf=min(d[2*i].suf*d[2*i+1].sm, mx);
d[i].p=d[2*i].p;
}
}
} s;
int init(int N, int X[], int Y[]) {
n=N;
x.resize(N+1); y.resize(N+1);
for (int i=1; i<=N; i++) x[i]=X[i-1], y[i]=Y[i-1], s.update(1, n, 1, i, x[i], y[i]);
return (int)s.d[1].ans;
}
int updateX(int pos, int val) {
x[pos+1]=val;
s.update(1, n, 1, pos+1, x[pos+1], y[pos+1]);
return (int)s.d[1].ans;
}
int updateY(int pos, int val) {
y[pos+1]=val;
s.update(1, n, 1, pos+1, x[pos+1], y[pos+1]);
return (int)s.d[1].ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 8 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 11 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 18 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 19 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 20 |
Correct |
3 ms |
8284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 8 |
Correct |
4 ms |
8024 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 11 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 12 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 20 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 21 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 22 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 23 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 24 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 25 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 26 |
Correct |
4 ms |
8296 KB |
Output is correct |
| 27 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 28 |
Correct |
3 ms |
8300 KB |
Output is correct |
| 29 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 30 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 31 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 32 |
Correct |
3 ms |
8296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
62584 KB |
Output is correct |
| 2 |
Correct |
296 ms |
75148 KB |
Output is correct |
| 3 |
Correct |
260 ms |
66228 KB |
Output is correct |
| 4 |
Correct |
292 ms |
70172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 8 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 11 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 12 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 15 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 17 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 20 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 23 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 24 |
Correct |
3 ms |
8416 KB |
Output is correct |
| 25 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 26 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 27 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 28 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 29 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 30 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 31 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 32 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 33 |
Correct |
173 ms |
65520 KB |
Output is correct |
| 34 |
Correct |
162 ms |
65516 KB |
Output is correct |
| 35 |
Correct |
217 ms |
72444 KB |
Output is correct |
| 36 |
Correct |
176 ms |
72436 KB |
Output is correct |
| 37 |
Correct |
151 ms |
63716 KB |
Output is correct |
| 38 |
Correct |
165 ms |
64644 KB |
Output is correct |
| 39 |
Correct |
175 ms |
63420 KB |
Output is correct |
| 40 |
Correct |
179 ms |
67684 KB |
Output is correct |
| 41 |
Correct |
166 ms |
63724 KB |
Output is correct |
| 42 |
Correct |
150 ms |
63568 KB |
Output is correct |
| 43 |
Correct |
164 ms |
67972 KB |
Output is correct |
| 44 |
Correct |
187 ms |
67928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8024 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 5 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 7 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 8 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 11 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 12 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8028 KB |
Output is correct |
| 15 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 17 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 20 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 23 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 24 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 25 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 26 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 27 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 28 |
Correct |
4 ms |
8280 KB |
Output is correct |
| 29 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 30 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 31 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 32 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 33 |
Correct |
181 ms |
66396 KB |
Output is correct |
| 34 |
Correct |
254 ms |
75012 KB |
Output is correct |
| 35 |
Correct |
226 ms |
66340 KB |
Output is correct |
| 36 |
Correct |
246 ms |
70064 KB |
Output is correct |
| 37 |
Correct |
170 ms |
65580 KB |
Output is correct |
| 38 |
Correct |
158 ms |
65616 KB |
Output is correct |
| 39 |
Correct |
175 ms |
72372 KB |
Output is correct |
| 40 |
Correct |
174 ms |
72272 KB |
Output is correct |
| 41 |
Correct |
150 ms |
63568 KB |
Output is correct |
| 42 |
Correct |
148 ms |
64604 KB |
Output is correct |
| 43 |
Correct |
136 ms |
63824 KB |
Output is correct |
| 44 |
Correct |
172 ms |
67412 KB |
Output is correct |
| 45 |
Correct |
140 ms |
63580 KB |
Output is correct |
| 46 |
Correct |
136 ms |
63568 KB |
Output is correct |
| 47 |
Correct |
158 ms |
67860 KB |
Output is correct |
| 48 |
Correct |
169 ms |
67792 KB |
Output is correct |
| 49 |
Correct |
232 ms |
67408 KB |
Output is correct |
| 50 |
Correct |
238 ms |
67416 KB |
Output is correct |
| 51 |
Correct |
203 ms |
74424 KB |
Output is correct |
| 52 |
Correct |
218 ms |
73940 KB |
Output is correct |
| 53 |
Correct |
219 ms |
65872 KB |
Output is correct |
| 54 |
Correct |
191 ms |
66512 KB |
Output is correct |
| 55 |
Correct |
173 ms |
64596 KB |
Output is correct |
| 56 |
Correct |
197 ms |
69360 KB |
Output is correct |
| 57 |
Correct |
174 ms |
65176 KB |
Output is correct |
| 58 |
Correct |
177 ms |
65884 KB |
Output is correct |
| 59 |
Correct |
156 ms |
67756 KB |
Output is correct |
