| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 601579 |
2022-07-22T08:16:15 Z |
Vanilla |
Horses (IOI15_horses) |
C++17 |
|
718 ms |
67008 KB |
#include <bits/stdc++.h>
#include "horses.h"
typedef long long int64;
using namespace std;
const int64 mod = 1e9 + 7;
const int maxn = 5e5 + 2;
int n;
struct node {
int64 v;
int64 x;
int64 y;
double dv;
double dx;
double dy;
} sgt [4 * maxn];
node merge (node a, node b) {
node rs;
b.dx+=a.dx, b.dv+=a.dx;
if (a.dv > b.dv) rs.v = a.v, rs.dv = a.dv;
else rs.v = a.x * b.v % mod, rs.dv = b.dv;
rs.x = a.x * b.x % mod;
rs.dx = b.dx;
return rs;
}
node update (int x, int l, int r, int ps, int64 vx, int64 vy) {
if (l > ps || r < ps) return sgt[x];
if (l == r && l == ps) {
node& nd = sgt[x];
if (vx) nd.dx = log(vx), nd.x = vx;
if (vy) nd.dy = log(vy), nd.y = vy;
nd.v = nd.x * nd.y % mod, nd.dv = nd.dx + nd.dy;
return nd;
}
int mid = (l + r) / 2;
return sgt[x] = merge(update(x * 2, l, mid, ps, vx, vy), update(x * 2 + 1, mid + 1, r, ps, vx, vy));
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < N; i++){
update(1, 0, n - 1, i, X[i], Y[i]);
}
return sgt[1].v;
}
int updateX(int pos, int val) {
update(1, 0, n - 1, pos, val, 0);
return sgt[1].v;
}
int updateY(int pos, int val) {
update(1, 0, n - 1, pos, 0, val);
return sgt[1].v;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:45:16: warning: conversion from 'int64' {aka 'long long int'} to 'int' may change value [-Wconversion]
45 | return sgt[1].v;
| ~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:50:16: warning: conversion from 'int64' {aka 'long long int'} to 'int' may change value [-Wconversion]
50 | return sgt[1].v;
| ~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:55:16: warning: conversion from 'int64' {aka 'long long int'} to 'int' may change value [-Wconversion]
55 | return sgt[1].v;
| ~~~~~~~^
| # |
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 |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 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 |
212 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 |
312 KB |
Output is correct |
| 15 |
Correct |
1 ms |
308 KB |
Output is correct |
| 16 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
360 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 |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
304 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 |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
232 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 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 |
316 KB |
Output is correct |
| 23 |
Correct |
3 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
348 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
328 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
2 ms |
320 KB |
Output is correct |
| 30 |
Correct |
2 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
54424 KB |
Output is correct |
| 2 |
Correct |
633 ms |
66952 KB |
Output is correct |
| 3 |
Correct |
594 ms |
58364 KB |
Output is correct |
| 4 |
Correct |
718 ms |
61984 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 |
1 ms |
316 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 |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
316 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 |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
304 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
308 KB |
Output is correct |
| 20 |
Correct |
1 ms |
312 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
456 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
320 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
2 ms |
316 KB |
Output is correct |
| 30 |
Correct |
2 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 |
469 ms |
57444 KB |
Output is correct |
| 34 |
Correct |
435 ms |
57420 KB |
Output is correct |
| 35 |
Correct |
490 ms |
64424 KB |
Output is correct |
| 36 |
Correct |
471 ms |
64332 KB |
Output is correct |
| 37 |
Correct |
411 ms |
55676 KB |
Output is correct |
| 38 |
Correct |
446 ms |
56536 KB |
Output is correct |
| 39 |
Correct |
422 ms |
55432 KB |
Output is correct |
| 40 |
Correct |
451 ms |
59512 KB |
Output is correct |
| 41 |
Correct |
458 ms |
55552 KB |
Output is correct |
| 42 |
Correct |
418 ms |
55560 KB |
Output is correct |
| 43 |
Correct |
436 ms |
59768 KB |
Output is correct |
| 44 |
Correct |
443 ms |
59832 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 |
1 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 |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 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 |
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 |
308 KB |
Output is correct |
| 16 |
Correct |
1 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 |
1 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 |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
436 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
448 KB |
Output is correct |
| 27 |
Correct |
2 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
2 ms |
340 KB |
Output is correct |
| 30 |
Correct |
2 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 |
477 ms |
58240 KB |
Output is correct |
| 34 |
Correct |
545 ms |
67008 KB |
Output is correct |
| 35 |
Correct |
556 ms |
58152 KB |
Output is correct |
| 36 |
Correct |
532 ms |
62088 KB |
Output is correct |
| 37 |
Correct |
441 ms |
57572 KB |
Output is correct |
| 38 |
Correct |
409 ms |
57388 KB |
Output is correct |
| 39 |
Correct |
424 ms |
64608 KB |
Output is correct |
| 40 |
Correct |
454 ms |
64360 KB |
Output is correct |
| 41 |
Correct |
395 ms |
55616 KB |
Output is correct |
| 42 |
Correct |
450 ms |
56668 KB |
Output is correct |
| 43 |
Correct |
406 ms |
55432 KB |
Output is correct |
| 44 |
Correct |
452 ms |
59404 KB |
Output is correct |
| 45 |
Correct |
447 ms |
55500 KB |
Output is correct |
| 46 |
Correct |
443 ms |
55620 KB |
Output is correct |
| 47 |
Correct |
466 ms |
59752 KB |
Output is correct |
| 48 |
Correct |
455 ms |
59852 KB |
Output is correct |
| 49 |
Correct |
610 ms |
59496 KB |
Output is correct |
| 50 |
Correct |
571 ms |
59492 KB |
Output is correct |
| 51 |
Correct |
593 ms |
66268 KB |
Output is correct |
| 52 |
Correct |
583 ms |
65716 KB |
Output is correct |
| 53 |
Correct |
604 ms |
57840 KB |
Output is correct |
| 54 |
Correct |
678 ms |
58292 KB |
Output is correct |
| 55 |
Correct |
523 ms |
56532 KB |
Output is correct |
| 56 |
Correct |
546 ms |
61268 KB |
Output is correct |
| 57 |
Correct |
570 ms |
57216 KB |
Output is correct |
| 58 |
Correct |
522 ms |
57748 KB |
Output is correct |
| 59 |
Correct |
433 ms |
59772 KB |
Output is correct |
