| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1041283 |
2024-08-01T20:07:00 Z |
allin27x |
Horses (IOI15_horses) |
C++17 |
|
48 ms |
53588 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[N];
int X[N], Y[N];
node merge(node a, node b){
node res; return res;
int p = a.r * b.l; if (p>1e9) p = 0;
if (!p || p * b.y > a.y){
//right is better
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:21:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
21 | 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:21:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
21 | 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:26:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
26 | 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:26:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
26 | 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:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int m = l + r >> 1;
| ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:47:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
47 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:52:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
52 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:57:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
57 | return (t[1].lm*t[1].y) % mod;
| ~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
48 ms |
53588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
