| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 583901 |
2022-06-26T12:57:42 Z |
M_W |
Horses (IOI15_horses) |
C++17 |
|
943 ms |
40356 KB |
#include <bits/stdc++.h>
using namespace std;
long long tp[500001 << 2], tmd[500001 << 2], Y[500001], X[500001];
const long long md = 1e9 + 7;
int N;
void upd_product(int v, int tl, int tr, int pos, int val){
if(tl == pos && tl == tr){
tp[v] = tmd[v] = val * 1ll;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) upd_product(v * 2, tl, tm, pos, val);
else upd_product(v * 2 + 1, tm + 1, tr, pos, val);
tmd[v] = ((tmd[v * 2] % md) * (tmd[v * 2 + 1] % md)) % md;
tp[v] = tp[v * 2] * tp[v * 2 + 1];
if(abs(tp[v]) > md || tp[v * 2] == -1 || tp[v * 2 + 1] == -1) tp[v] = -1;
}
long long query_product(int v, int tl, int tr, int l, int r){
if(l > r) return 1ll;
if(tl == l && tr == r) return tp[v];
int tm = (tl + tr) >> 1;
long long left = query_product(v * 2, tl, tm, l, min(r, tm));
long long right = query_product(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
if(left == -1ll || right == -1ll || left * right > md) return -1ll;
return left * right;
}
long long query_md(int v, int tl, int tr, int l, int r){
if(l > r) return 1ll;
if(tl == l && tr == r) return tmd[v];
int tm = (tl + tr) >> 1;
long long left = query_md(v * 2, tl, tm, l, min(r, tm));
long long right = query_md(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
return (left * right) % md;
}
// Actual query tree
int t[500001 << 2];
void build(int v, int tl, int tr){
if(tl == tr){
t[v] = tl;
return;
}
int tm = (tl + tr) >> 1;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
long long Yl = Y[t[v * 2]], Yr = Y[t[v * 2 + 1]];
long long prod = query_product(1, 0, N - 1, t[v * 2] + 1, t[v * 2 + 1]);
if(prod == -1ll || prod * Yr > Yl) t[v] = t[v * 2 + 1];
else t[v] = t[v * 2];
}
void ins(int v, int tl, int tr, int pos){
if(tl == pos && tl == tr) return;
int tm = (tl + tr) >> 1;
if(pos <= tm) ins(v * 2, tl, tm, pos);
else ins(v * 2 + 1, tm + 1, tr, pos);
long long Yl = Y[t[v * 2]], Yr = Y[t[v * 2 + 1]];
long long prod = query_product(1, 0, N - 1, t[v * 2] + 1, t[v * 2 + 1]);
if(prod == -1ll || prod * Yr > Yl) t[v] = t[v * 2 + 1];
else t[v] = t[v * 2];
}
int cur;
int init(int N_tmp, int X_tmp[], int Y_tmp[]){
N = N_tmp;
for(int i = 0; i < N; i++) X[i] = X_tmp[i] * 1ll;
for(int i = 0; i < N; i++) upd_product(1, 0, N - 1, i, X[i]);
for(int i = 0; i < N; i++) Y[i] = Y_tmp[i] * 1ll;
build(1, 0, N - 1);
return int((query_md(1, 0, N - 1, 0, t[1]) * Y[t[1]]) % md);
}
int updateX(int pos, int val){
X[pos] = val;
upd_product(1, 0, N - 1, pos, val);
ins(1, 0, N - 1, pos);
return int((query_md(1, 0, N - 1, 0, t[1]) * Y[t[1]]) % md);
}
int updateY(int pos, int val){
Y[pos] = val;
ins(1, 0, N - 1, pos);
return int((query_md(1, 0, N - 1, 0, t[1]) * Y[t[1]]) % md);
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:60: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
83 | for(int i = 0; i < N; i++) upd_product(1, 0, N - 1, i, X[i]);
| ~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
276 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
308 KB |
Output is correct |
| 16 |
Correct |
1 ms |
308 KB |
Output is correct |
| 17 |
Correct |
1 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
304 KB |
Output is correct |
| 20 |
Correct |
1 ms |
308 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
2 ms |
320 KB |
Output is correct |
| 24 |
Correct |
3 ms |
340 KB |
Output is correct |
| 25 |
Correct |
3 ms |
320 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
3 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
320 KB |
Output is correct |
| 29 |
Correct |
2 ms |
340 KB |
Output is correct |
| 30 |
Correct |
3 ms |
320 KB |
Output is correct |
| 31 |
Correct |
3 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
609 ms |
33752 KB |
Output is correct |
| 2 |
Correct |
581 ms |
33820 KB |
Output is correct |
| 3 |
Correct |
684 ms |
33780 KB |
Output is correct |
| 4 |
Correct |
704 ms |
33800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
312 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
304 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
304 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
3 ms |
324 KB |
Output is correct |
| 24 |
Correct |
3 ms |
316 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
320 KB |
Output is correct |
| 27 |
Correct |
3 ms |
340 KB |
Output is correct |
| 28 |
Correct |
3 ms |
340 KB |
Output is correct |
| 29 |
Correct |
3 ms |
340 KB |
Output is correct |
| 30 |
Correct |
3 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
321 ms |
32936 KB |
Output is correct |
| 34 |
Correct |
328 ms |
32872 KB |
Output is correct |
| 35 |
Correct |
300 ms |
33120 KB |
Output is correct |
| 36 |
Correct |
295 ms |
32952 KB |
Output is correct |
| 37 |
Correct |
298 ms |
32904 KB |
Output is correct |
| 38 |
Correct |
272 ms |
33044 KB |
Output is correct |
| 39 |
Correct |
272 ms |
32820 KB |
Output is correct |
| 40 |
Correct |
286 ms |
32900 KB |
Output is correct |
| 41 |
Correct |
269 ms |
33056 KB |
Output is correct |
| 42 |
Correct |
299 ms |
32968 KB |
Output is correct |
| 43 |
Correct |
241 ms |
32836 KB |
Output is correct |
| 44 |
Correct |
255 ms |
32844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
308 KB |
Output is correct |
| 15 |
Correct |
1 ms |
300 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
308 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
2 ms |
424 KB |
Output is correct |
| 24 |
Correct |
3 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
320 KB |
Output is correct |
| 27 |
Correct |
3 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
3 ms |
340 KB |
Output is correct |
| 30 |
Correct |
3 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
536 ms |
33792 KB |
Output is correct |
| 34 |
Correct |
606 ms |
33776 KB |
Output is correct |
| 35 |
Correct |
721 ms |
33836 KB |
Output is correct |
| 36 |
Correct |
710 ms |
33744 KB |
Output is correct |
| 37 |
Correct |
306 ms |
32920 KB |
Output is correct |
| 38 |
Correct |
348 ms |
32832 KB |
Output is correct |
| 39 |
Correct |
293 ms |
32936 KB |
Output is correct |
| 40 |
Correct |
282 ms |
32884 KB |
Output is correct |
| 41 |
Correct |
322 ms |
32980 KB |
Output is correct |
| 42 |
Correct |
291 ms |
32844 KB |
Output is correct |
| 43 |
Correct |
287 ms |
32800 KB |
Output is correct |
| 44 |
Correct |
275 ms |
32828 KB |
Output is correct |
| 45 |
Correct |
271 ms |
32880 KB |
Output is correct |
| 46 |
Correct |
266 ms |
32916 KB |
Output is correct |
| 47 |
Correct |
272 ms |
32844 KB |
Output is correct |
| 48 |
Correct |
252 ms |
32848 KB |
Output is correct |
| 49 |
Correct |
943 ms |
33868 KB |
Output is correct |
| 50 |
Correct |
863 ms |
33808 KB |
Output is correct |
| 51 |
Correct |
562 ms |
33808 KB |
Output is correct |
| 52 |
Correct |
469 ms |
33832 KB |
Output is correct |
| 53 |
Correct |
926 ms |
33820 KB |
Output is correct |
| 54 |
Correct |
557 ms |
37572 KB |
Output is correct |
| 55 |
Correct |
715 ms |
35924 KB |
Output is correct |
| 56 |
Correct |
633 ms |
40356 KB |
Output is correct |
| 57 |
Correct |
622 ms |
36324 KB |
Output is correct |
| 58 |
Correct |
690 ms |
36832 KB |
Output is correct |
| 59 |
Correct |
262 ms |
38992 KB |
Output is correct |
