| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 342811 |
2021-01-02T21:42:45 Z |
monus1042 |
Horses (IOI15_horses) |
C++17 |
|
720 ms |
131504 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> ii;
typedef long double ld;
const ll MOD = 1000000007;
const int MAXS = 5e5+10;
int n;
vector<ll> x, y;
vector<ld> accbasis;
vector<pair<ld, int>> seg(MAXS * 4);
vector<ld> lazy(MAXS *4);
vector<ll> fen(MAXS, 1LL); // using 1 indexing in this
ll power(ll b, ll exp){
if (exp == 0) return 1LL;
if (exp&1) return (power((b*b) % MOD, exp/2) * b) % MOD;
return power((b*b)%MOD, exp/2) % MOD;
}
void build(int node, int l, int r){
if (l == r){
seg[node] = make_pair(accbasis[l], l);
return;
}
int mid = (l + r) / 2;
build(node *2, l, mid);
build(node*2 +1, mid+1, r);
if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
else seg[node] = seg[node*2+1];
}
void update(int node, int l, int r, int xl, int xr, ld delta){
if (lazy[node] != 0.0){
seg[node].first += lazy[node];
if (l!=r){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0.0;
}
if (l > xr || r < xl) return;
if (xl <= l && r <= xr){
seg[node].first += delta;
if (l != r){
lazy[node*2] += delta;
lazy[node*2+1] += delta;
}
return;
}
int mid = (l+r)/2;
update(node*2, l, mid, xl, xr, delta);
update(node*2+1, mid+1, r, xl, xr, delta);
if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
else seg[node] = seg[node*2+1];
}
void upd(int pos, ll factor){
while(pos <= n){
fen[pos] = (fen[pos] * factor) % MOD;
pos += pos&-pos;
}
}
ll que(int pos){
ll answer = 1LL;
while(pos){
answer = (answer * fen[pos]) % MOD;
pos -= pos&-pos;
}
return answer;
}
int solve(){
int position = seg[1].second + 1;
ll answer = (que(position) * y[position-1]) % MOD;
return (int)answer;
}
int init(int N, int X[], int Y[]) {
n = N;
for (int i=0; i<n; i++) x.push_back(X[i]), y.push_back(Y[i]);
ld acc = 0.0;
for (int i=0; i<n; i++){
acc = acc + (ld)log10(x[i]);
accbasis.push_back(acc);
upd(i+1, x[i]);
}
build(1, 0, n-1);
for (int i=0; i<n; i++){
update(1, 0, n-1, i, i, (ld)log10(y[i]));
}
return solve();
}
int updateX(int pos, int val) {
ll inv = power(x[pos], MOD-2);
upd(pos+1, inv);
upd(pos+1, (ll)val);
ld delta = (ld)log10(val) - (ld)log10(x[pos]);
update(1, 0, n-1, pos, n-1, delta);
x[pos] = val;
return solve();
}
int updateY(int pos, int val) {
ld delta = (ld)log10(val) - log10(y[pos]);
update(1, 0, n-1, pos, pos, delta);
y[pos] = val;
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 2 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 3 |
Correct |
63 ms |
98156 KB |
Output is correct |
| 4 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 5 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 6 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 7 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 8 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 9 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 10 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 11 |
Correct |
64 ms |
98156 KB |
Output is correct |
| 12 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 13 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 14 |
Correct |
56 ms |
98196 KB |
Output is correct |
| 15 |
Correct |
57 ms |
98188 KB |
Output is correct |
| 16 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 17 |
Correct |
61 ms |
98284 KB |
Output is correct |
| 18 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 19 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 20 |
Correct |
54 ms |
98176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
98284 KB |
Output is correct |
| 2 |
Correct |
54 ms |
98176 KB |
Output is correct |
| 3 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 4 |
Correct |
57 ms |
98284 KB |
Output is correct |
| 5 |
Correct |
54 ms |
98200 KB |
Output is correct |
| 6 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 7 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 8 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 9 |
Correct |
54 ms |
98284 KB |
Output is correct |
| 10 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 11 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 12 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 13 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 14 |
Correct |
53 ms |
98284 KB |
Output is correct |
| 15 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 16 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 17 |
Correct |
63 ms |
98156 KB |
Output is correct |
| 18 |
Correct |
59 ms |
98156 KB |
Output is correct |
| 19 |
Correct |
59 ms |
98156 KB |
Output is correct |
| 20 |
Correct |
57 ms |
98156 KB |
Output is correct |
| 21 |
Correct |
54 ms |
98284 KB |
Output is correct |
| 22 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 23 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 24 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 25 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 26 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 27 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 28 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 29 |
Correct |
62 ms |
98224 KB |
Output is correct |
| 30 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 31 |
Correct |
54 ms |
98412 KB |
Output is correct |
| 32 |
Correct |
55 ms |
98284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
455 ms |
119780 KB |
Output is correct |
| 2 |
Correct |
720 ms |
125532 KB |
Output is correct |
| 3 |
Correct |
629 ms |
122672 KB |
Output is correct |
| 4 |
Correct |
689 ms |
125628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 2 |
Correct |
54 ms |
98160 KB |
Output is correct |
| 3 |
Correct |
57 ms |
98284 KB |
Output is correct |
| 4 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 5 |
Correct |
55 ms |
98176 KB |
Output is correct |
| 6 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 7 |
Correct |
54 ms |
98168 KB |
Output is correct |
| 8 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 9 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 10 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 11 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 12 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 13 |
Correct |
54 ms |
98212 KB |
Output is correct |
| 14 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 15 |
Correct |
57 ms |
98156 KB |
Output is correct |
| 16 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 17 |
Correct |
53 ms |
98156 KB |
Output is correct |
| 18 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 19 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 20 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 21 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 22 |
Correct |
58 ms |
98156 KB |
Output is correct |
| 23 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 24 |
Correct |
64 ms |
98284 KB |
Output is correct |
| 25 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 26 |
Correct |
54 ms |
98284 KB |
Output is correct |
| 27 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 28 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 29 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 30 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 31 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 32 |
Correct |
58 ms |
98292 KB |
Output is correct |
| 33 |
Correct |
442 ms |
118856 KB |
Output is correct |
| 34 |
Correct |
430 ms |
122184 KB |
Output is correct |
| 35 |
Correct |
442 ms |
129212 KB |
Output is correct |
| 36 |
Correct |
442 ms |
129084 KB |
Output is correct |
| 37 |
Correct |
392 ms |
120388 KB |
Output is correct |
| 38 |
Correct |
425 ms |
121404 KB |
Output is correct |
| 39 |
Correct |
379 ms |
120392 KB |
Output is correct |
| 40 |
Correct |
413 ms |
124220 KB |
Output is correct |
| 41 |
Correct |
372 ms |
120392 KB |
Output is correct |
| 42 |
Correct |
370 ms |
120388 KB |
Output is correct |
| 43 |
Correct |
395 ms |
124612 KB |
Output is correct |
| 44 |
Correct |
396 ms |
124604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
98188 KB |
Output is correct |
| 2 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 3 |
Correct |
54 ms |
98192 KB |
Output is correct |
| 4 |
Correct |
55 ms |
98156 KB |
Output is correct |
| 5 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 6 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 7 |
Correct |
61 ms |
98284 KB |
Output is correct |
| 8 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 9 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 10 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 11 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 12 |
Correct |
57 ms |
98156 KB |
Output is correct |
| 13 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 14 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 15 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 16 |
Correct |
61 ms |
98156 KB |
Output is correct |
| 17 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 18 |
Correct |
57 ms |
98156 KB |
Output is correct |
| 19 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 20 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 21 |
Correct |
56 ms |
98156 KB |
Output is correct |
| 22 |
Correct |
54 ms |
98156 KB |
Output is correct |
| 23 |
Correct |
58 ms |
98284 KB |
Output is correct |
| 24 |
Correct |
56 ms |
98304 KB |
Output is correct |
| 25 |
Correct |
55 ms |
98260 KB |
Output is correct |
| 26 |
Correct |
56 ms |
98412 KB |
Output is correct |
| 27 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 28 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 29 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 30 |
Correct |
55 ms |
98284 KB |
Output is correct |
| 31 |
Correct |
54 ms |
98284 KB |
Output is correct |
| 32 |
Correct |
56 ms |
98284 KB |
Output is correct |
| 33 |
Correct |
447 ms |
121136 KB |
Output is correct |
| 34 |
Correct |
710 ms |
131504 KB |
Output is correct |
| 35 |
Correct |
635 ms |
122708 KB |
Output is correct |
| 36 |
Correct |
702 ms |
126480 KB |
Output is correct |
| 37 |
Correct |
429 ms |
122300 KB |
Output is correct |
| 38 |
Correct |
435 ms |
122184 KB |
Output is correct |
| 39 |
Correct |
442 ms |
129240 KB |
Output is correct |
| 40 |
Correct |
468 ms |
129060 KB |
Output is correct |
| 41 |
Correct |
383 ms |
120380 KB |
Output is correct |
| 42 |
Correct |
410 ms |
121304 KB |
Output is correct |
| 43 |
Correct |
377 ms |
120380 KB |
Output is correct |
| 44 |
Correct |
415 ms |
124220 KB |
Output is correct |
| 45 |
Correct |
370 ms |
120388 KB |
Output is correct |
| 46 |
Correct |
372 ms |
120392 KB |
Output is correct |
| 47 |
Correct |
394 ms |
124664 KB |
Output is correct |
| 48 |
Correct |
397 ms |
124616 KB |
Output is correct |
| 49 |
Correct |
675 ms |
123968 KB |
Output is correct |
| 50 |
Correct |
676 ms |
123952 KB |
Output is correct |
| 51 |
Correct |
524 ms |
130868 KB |
Output is correct |
| 52 |
Correct |
543 ms |
130224 KB |
Output is correct |
| 53 |
Correct |
601 ms |
122416 KB |
Output is correct |
| 54 |
Correct |
551 ms |
122928 KB |
Output is correct |
| 55 |
Correct |
512 ms |
121252 KB |
Output is correct |
| 56 |
Correct |
578 ms |
125688 KB |
Output is correct |
| 57 |
Correct |
438 ms |
121648 KB |
Output is correct |
| 58 |
Correct |
464 ms |
122160 KB |
Output is correct |
| 59 |
Correct |
397 ms |
124724 KB |
Output is correct |
