| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1041317 |
2024-08-01T21:20:03 Z |
allin27x |
Horses (IOI15_horses) |
C++17 |
|
261 ms |
66640 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
struct node{
int l=1,r=1,lm=1,rm=1,y=1;
};
const int N = 5e5+5;
node t[4*N];
int X[N], Y[N];
node merge(node a, node b){
node res;
int p = a.r * b.l; if (p>1e9) p = 0;
if (!p || p * b.y > a.y){
res.y = b.y;
res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
res.r = b.r; res.rm = b.rm;
res.lm = (a.lm*a.rm)%mod; res.lm*=b.lm; res.lm%=mod;
} else {
res.y = a.y; res.l=a.l; res.lm=a.lm;
res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
res.rm=(b.lm*b.rm)%mod; res.rm*=a.rm; res.rm%=mod;
}
return res;
}
void update(int p, int l, int r, int i){
if (l==r){
t[p].l=X[i]; t[p].lm=X[i]; t[p].y=Y[i];
return;
}
int m = l + r >> 1;
if (m>=i) update(2*p, l, m, i);
else update(2*p+1, m+1, r, i);
t[p] = merge(t[2*p], t[2*p+1]);
}
signed init(signed n, signed x[], signed y[]){
for (int i=0; i<n; i++) X[i] = x[i], Y[i]=y[i];
for (int i=0; i<n; i++) update(1, 0, N-1, i);
return (t[1].lm*t[1].y) % mod;
}
signed updateX(signed pos, signed val){
X[pos] = val; update(1, 0, N-1, pos);
return (t[1].lm*t[1].y) % mod;
}
signed updateY(signed pos, signed val){
Y[pos] = val; update(1, 0, N-1, pos);
return (t[1].lm*t[1].y) % mod;
}
Compilation message
horses.cpp: In function 'node merge(node, node)':
horses.cpp:17:28: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
17 | int p = a.r * b.l; if (p>1e9) p = 0;
| ^
horses.cpp:20:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
20 | res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
| ~~~~^
horses.cpp:20:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
20 | res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
| ~~~~^
horses.cpp:25:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
25 | res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
| ~~~~^
horses.cpp:25:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
25 | res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
| ~~~~^
horses.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
horses.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:46:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
46 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:51:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
51 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:56:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
56 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
54096 KB |
Output is correct |
| 2 |
Correct |
254 ms |
66640 KB |
Output is correct |
| 3 |
Correct |
237 ms |
57940 KB |
Output is correct |
| 4 |
Correct |
258 ms |
61776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 33 |
Correct |
191 ms |
57168 KB |
Output is correct |
| 34 |
Correct |
197 ms |
57168 KB |
Output is correct |
| 35 |
Correct |
193 ms |
64080 KB |
Output is correct |
| 36 |
Correct |
188 ms |
64180 KB |
Output is correct |
| 37 |
Correct |
189 ms |
55376 KB |
Output is correct |
| 38 |
Correct |
177 ms |
56144 KB |
Output is correct |
| 39 |
Correct |
180 ms |
55120 KB |
Output is correct |
| 40 |
Correct |
182 ms |
59140 KB |
Output is correct |
| 41 |
Correct |
180 ms |
55120 KB |
Output is correct |
| 42 |
Correct |
185 ms |
55376 KB |
Output is correct |
| 43 |
Correct |
174 ms |
59472 KB |
Output is correct |
| 44 |
Correct |
185 ms |
59464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2904 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 33 |
Correct |
196 ms |
57780 KB |
Output is correct |
| 34 |
Correct |
258 ms |
66540 KB |
Output is correct |
| 35 |
Correct |
224 ms |
57936 KB |
Output is correct |
| 36 |
Correct |
248 ms |
61776 KB |
Output is correct |
| 37 |
Correct |
198 ms |
57168 KB |
Output is correct |
| 38 |
Correct |
196 ms |
57168 KB |
Output is correct |
| 39 |
Correct |
192 ms |
64080 KB |
Output is correct |
| 40 |
Correct |
196 ms |
64080 KB |
Output is correct |
| 41 |
Correct |
188 ms |
55292 KB |
Output is correct |
| 42 |
Correct |
170 ms |
56144 KB |
Output is correct |
| 43 |
Correct |
179 ms |
55120 KB |
Output is correct |
| 44 |
Correct |
198 ms |
59216 KB |
Output is correct |
| 45 |
Correct |
182 ms |
55120 KB |
Output is correct |
| 46 |
Correct |
184 ms |
55204 KB |
Output is correct |
| 47 |
Correct |
176 ms |
59472 KB |
Output is correct |
| 48 |
Correct |
179 ms |
59528 KB |
Output is correct |
| 49 |
Correct |
258 ms |
59228 KB |
Output is correct |
| 50 |
Correct |
261 ms |
59068 KB |
Output is correct |
| 51 |
Correct |
225 ms |
65872 KB |
Output is correct |
| 52 |
Correct |
225 ms |
65296 KB |
Output is correct |
| 53 |
Correct |
261 ms |
57428 KB |
Output is correct |
| 54 |
Correct |
205 ms |
57936 KB |
Output is correct |
| 55 |
Correct |
219 ms |
56144 KB |
Output is correct |
| 56 |
Correct |
211 ms |
61008 KB |
Output is correct |
| 57 |
Correct |
217 ms |
57168 KB |
Output is correct |
| 58 |
Correct |
214 ms |
57428 KB |
Output is correct |
| 59 |
Correct |
176 ms |
59468 KB |
Output is correct |
