| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1041316 |
2024-08-01T21:11:56 Z |
allin27x |
Horses (IOI15_horses) |
C++17 |
|
212 ms |
56980 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*a.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 |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
0 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 |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2648 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 |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2556 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 |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 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 |
0 ms |
2396 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 |
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 |
0 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
56980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 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 |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2648 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 |
2396 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 |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
2396 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 |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2648 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 |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 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 |
| 21 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 22 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
