| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 513850 |
2022-01-17T17:52:21 Z |
sliviu |
Horses (IOI15_horses) |
C++14 |
|
149 ms |
50372 KB |
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
const int mod = 1e9 + 7;
int n, x[1 << 19], y[1 << 19];
struct node {
int ans, x, y;
double rans, rx, ry;
} st[1 << 20];
node Merge(node l, node r) {
node ans;
ans.x = 1LL * l.x * r.x % mod;
ans.rx = l.rx + r.rx;
if (l.rans > l.rx + r.rans)
ans.ans = l.ans, ans.rans = l.rans;
else
ans.ans = 1LL * l.x * r.ans % mod, ans.rans = l.rx + r.rans;
return ans;
}
void Build(int node = 1, int left = 1, int right = n) {
if (left == right) {
st[node].x = x[left - 1];
st[node].rx = log(x[left - 1]);
st[node].ry = log(y[left - 1]);
st[node].y = y[left - 1];
st[node].ans = 1LL * st[node].x * st[node].y % mod;
st[node].rans = st[node].rx + st[node].ry;
return;
}
int m = (left + right) / 2;
Build(2 * node, left, m), Build(2 * node + 1, m + 1, right);
st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
void Update(int pos, pair<int, int> val, int node = 1, int left = 1, int right = n) {
if (left == right) {
if (val.first) {
st[node].x = val.first;
st[node].rx = log(val.first);
}
else {
st[node].y = val.second;
st[node].ry = log(val.second);
}
st[node].ans = 1LL * st[node].x * st[node].y % mod;
st[node].rans = st[node].rx + st[node].ry;
return;
}
int m = (left + right) / 2;
if (pos <= m)
Update(pos, val, 2 * node, left, m);
else
Update(pos, val, 2 * node + 1, m + 1, right);
st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i = 0; i < n; ++i)
x[i] = X[i], y[i] = Y[i];
Build();
return st[1].ans;
}
int updateX(int pos, int val) {
Update(pos + 1, {val,0});
return st[1].ans;
}
int updateY(int pos, int val) {
Update(pos + 1, {0, val});
return st[1].ans;
}
Compilation message
horses.cpp: In function 'node Merge(node, node)':
horses.cpp:16:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
16 | ans.x = 1LL * l.x * r.x % mod;
| ~~~~~~~~~~~~~~~~^~~~~
horses.cpp:21:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
21 | ans.ans = 1LL * l.x * r.ans % mod, ans.rans = l.rx + r.rans;
| ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Build(int, int, int)':
horses.cpp:31:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
31 | st[node].ans = 1LL * st[node].x * st[node].y % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void Update(int, std::pair<int, int>, int, int, int)':
horses.cpp:50:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
50 | st[node].ans = 1LL * st[node].x * st[node].y % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
280 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
300 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
296 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
300 KB |
Output is correct |
| 13 |
Correct |
0 ms |
296 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
0 ms |
204 KB |
Output is correct |
| 18 |
Correct |
0 ms |
204 KB |
Output is correct |
| 19 |
Correct |
0 ms |
204 KB |
Output is correct |
| 20 |
Correct |
0 ms |
204 KB |
Output is correct |
| 21 |
Correct |
0 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
436 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
50336 KB |
Output is correct |
| 2 |
Correct |
142 ms |
50284 KB |
Output is correct |
| 3 |
Correct |
104 ms |
50296 KB |
Output is correct |
| 4 |
Correct |
149 ms |
50372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
300 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
0 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
444 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
416 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| 33 |
Correct |
83 ms |
49420 KB |
Output is correct |
| 34 |
Correct |
75 ms |
49368 KB |
Output is correct |
| 35 |
Correct |
77 ms |
49436 KB |
Output is correct |
| 36 |
Correct |
78 ms |
49468 KB |
Output is correct |
| 37 |
Correct |
48 ms |
49424 KB |
Output is correct |
| 38 |
Correct |
47 ms |
49416 KB |
Output is correct |
| 39 |
Correct |
42 ms |
49304 KB |
Output is correct |
| 40 |
Correct |
56 ms |
49448 KB |
Output is correct |
| 41 |
Correct |
38 ms |
49328 KB |
Output is correct |
| 42 |
Correct |
39 ms |
49340 KB |
Output is correct |
| 43 |
Correct |
55 ms |
49372 KB |
Output is correct |
| 44 |
Correct |
55 ms |
49316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
300 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
296 KB |
Output is correct |
| 11 |
Correct |
1 ms |
304 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
0 ms |
204 KB |
Output is correct |
| 20 |
Correct |
0 ms |
204 KB |
Output is correct |
| 21 |
Correct |
0 ms |
204 KB |
Output is correct |
| 22 |
Correct |
0 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
432 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
304 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| 33 |
Correct |
74 ms |
50276 KB |
Output is correct |
| 34 |
Correct |
142 ms |
50340 KB |
Output is correct |
| 35 |
Correct |
108 ms |
50324 KB |
Output is correct |
| 36 |
Correct |
126 ms |
50344 KB |
Output is correct |
| 37 |
Correct |
55 ms |
49468 KB |
Output is correct |
| 38 |
Correct |
56 ms |
49552 KB |
Output is correct |
| 39 |
Correct |
75 ms |
49460 KB |
Output is correct |
| 40 |
Correct |
78 ms |
49604 KB |
Output is correct |
| 41 |
Correct |
41 ms |
49436 KB |
Output is correct |
| 42 |
Correct |
60 ms |
49416 KB |
Output is correct |
| 43 |
Correct |
38 ms |
49296 KB |
Output is correct |
| 44 |
Correct |
56 ms |
49484 KB |
Output is correct |
| 45 |
Correct |
38 ms |
49416 KB |
Output is correct |
| 46 |
Correct |
38 ms |
49344 KB |
Output is correct |
| 47 |
Correct |
54 ms |
49384 KB |
Output is correct |
| 48 |
Correct |
56 ms |
49416 KB |
Output is correct |
| 49 |
Correct |
117 ms |
50296 KB |
Output is correct |
| 50 |
Correct |
142 ms |
50336 KB |
Output is correct |
| 51 |
Correct |
105 ms |
50308 KB |
Output is correct |
| 52 |
Correct |
103 ms |
50352 KB |
Output is correct |
| 53 |
Correct |
106 ms |
50360 KB |
Output is correct |
| 54 |
Correct |
79 ms |
50244 KB |
Output is correct |
| 55 |
Correct |
66 ms |
49568 KB |
Output is correct |
| 56 |
Correct |
85 ms |
50252 KB |
Output is correct |
| 57 |
Correct |
68 ms |
50284 KB |
Output is correct |
| 58 |
Correct |
76 ms |
50324 KB |
Output is correct |
| 59 |
Correct |
53 ms |
49288 KB |
Output is correct |
