| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160537 |
2019-10-28T11:04:05 Z |
FiloSanza |
Horses (IOI15_horses) |
C++14 |
|
1251 ms |
40524 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9+7;
vector<pair<long long, bool>> segX;
vector<int> segY;
vector<int> Y;
int S;
inline int left(int i){return i*2+1;}
inline int right(int i){return (i+1)*2;}
inline int father(int i){return (i-1)/2;}
pair<long long, bool> mergeX(pair<long long, bool> a, pair<long long, bool> b){
long long val = (a.first * b.first);
bool o = val >= MOD || a.second || b.second;
return {val % MOD, o};
}
pair<long long, bool> queryX(int pos, int l, int h, int a, int b){
if(h < a || l > b) return {1, false};
if(l >= a && b >= h) return segX[pos];
int mid = (l+h)/2;
return mergeX(queryX(left(pos), l, mid, a, b), queryX(right(pos), mid+1, h, a, b));
}
int mergeY(int a, int b){
auto query = queryX(0, 0, S/2, a+1, b);
if(query.second) return b;
return Y[a] < 1LL * query.first * Y[b] ? b : a;
}
int init(int N, int X[], int Y[]) {
S = (1 << (int)ceil(log2(N) + 1)) - 1;
segX.resize(S, {1, false});
segY.resize(S, N);
::Y.resize(N);
for(int i=0; i<N; i++) ::Y[i] = Y[i];
::Y.push_back(0);
iota(segY.begin()+S/2, segY.begin()+S/2+N, 0);
for(int i=0; i<N; i++) segX[i+S/2] = {X[i], false};
for(int i=S/2-1; i>=0; i--){
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
int updateX(int i, int val) {
i += S/2;
segX[i].first = val;
while(i != 0){
i = father(i);
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
int updateY(int i, int val) {
Y[i] = val;
i += S/2;
while(i != 0){
i = father(i);
segX[i] = mergeX(segX[left(i)], segX[right(i)]);
segY[i] = mergeY(segY[left(i)], segY[right(i)]);
}
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:36:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
int init(int N, int X[], int Y[]) {
^
horses.cpp:10:13: note: shadowed declaration is here
vector<int> Y;
^
horses.cpp:52:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:76:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
380 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
252 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
252 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
1 ms |
128 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
6 ms |
292 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
256 KB |
Output is correct |
| 23 |
Correct |
4 ms |
504 KB |
Output is correct |
| 24 |
Correct |
4 ms |
504 KB |
Output is correct |
| 25 |
Correct |
4 ms |
504 KB |
Output is correct |
| 26 |
Correct |
3 ms |
380 KB |
Output is correct |
| 27 |
Correct |
4 ms |
376 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
5 ms |
376 KB |
Output is correct |
| 30 |
Correct |
4 ms |
504 KB |
Output is correct |
| 31 |
Correct |
4 ms |
376 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
719 ms |
31604 KB |
Output is correct |
| 2 |
Correct |
684 ms |
40524 KB |
Output is correct |
| 3 |
Correct |
813 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
795 ms |
35540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
252 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
380 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
256 KB |
Output is correct |
| 23 |
Correct |
4 ms |
504 KB |
Output is correct |
| 24 |
Correct |
4 ms |
404 KB |
Output is correct |
| 25 |
Correct |
4 ms |
504 KB |
Output is correct |
| 26 |
Correct |
3 ms |
504 KB |
Output is correct |
| 27 |
Correct |
5 ms |
376 KB |
Output is correct |
| 28 |
Correct |
4 ms |
380 KB |
Output is correct |
| 29 |
Correct |
4 ms |
376 KB |
Output is correct |
| 30 |
Correct |
4 ms |
504 KB |
Output is correct |
| 31 |
Correct |
4 ms |
376 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| 33 |
Correct |
301 ms |
32660 KB |
Output is correct |
| 34 |
Correct |
295 ms |
32632 KB |
Output is correct |
| 35 |
Correct |
259 ms |
39544 KB |
Output is correct |
| 36 |
Correct |
238 ms |
39544 KB |
Output is correct |
| 37 |
Correct |
291 ms |
30712 KB |
Output is correct |
| 38 |
Correct |
216 ms |
31736 KB |
Output is correct |
| 39 |
Correct |
260 ms |
30724 KB |
Output is correct |
| 40 |
Correct |
232 ms |
34552 KB |
Output is correct |
| 41 |
Correct |
269 ms |
30712 KB |
Output is correct |
| 42 |
Correct |
266 ms |
30712 KB |
Output is correct |
| 43 |
Correct |
193 ms |
35064 KB |
Output is correct |
| 44 |
Correct |
189 ms |
35024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
380 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
380 KB |
Output is correct |
| 15 |
Correct |
2 ms |
256 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
8 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
2 ms |
376 KB |
Output is correct |
| 23 |
Correct |
4 ms |
376 KB |
Output is correct |
| 24 |
Correct |
6 ms |
504 KB |
Output is correct |
| 25 |
Correct |
4 ms |
504 KB |
Output is correct |
| 26 |
Correct |
3 ms |
504 KB |
Output is correct |
| 27 |
Correct |
4 ms |
376 KB |
Output is correct |
| 28 |
Correct |
3 ms |
376 KB |
Output is correct |
| 29 |
Correct |
4 ms |
376 KB |
Output is correct |
| 30 |
Correct |
4 ms |
504 KB |
Output is correct |
| 31 |
Correct |
4 ms |
380 KB |
Output is correct |
| 32 |
Correct |
4 ms |
376 KB |
Output is correct |
| 33 |
Correct |
708 ms |
31544 KB |
Output is correct |
| 34 |
Correct |
634 ms |
40396 KB |
Output is correct |
| 35 |
Correct |
809 ms |
31720 KB |
Output is correct |
| 36 |
Correct |
789 ms |
35504 KB |
Output is correct |
| 37 |
Correct |
298 ms |
32632 KB |
Output is correct |
| 38 |
Correct |
295 ms |
32636 KB |
Output is correct |
| 39 |
Correct |
447 ms |
39544 KB |
Output is correct |
| 40 |
Correct |
231 ms |
39416 KB |
Output is correct |
| 41 |
Correct |
291 ms |
30840 KB |
Output is correct |
| 42 |
Correct |
215 ms |
31736 KB |
Output is correct |
| 43 |
Correct |
266 ms |
30760 KB |
Output is correct |
| 44 |
Correct |
233 ms |
34680 KB |
Output is correct |
| 45 |
Correct |
256 ms |
30712 KB |
Output is correct |
| 46 |
Correct |
261 ms |
30840 KB |
Output is correct |
| 47 |
Correct |
196 ms |
35064 KB |
Output is correct |
| 48 |
Correct |
189 ms |
35064 KB |
Output is correct |
| 49 |
Correct |
1199 ms |
32940 KB |
Output is correct |
| 50 |
Correct |
1233 ms |
32828 KB |
Output is correct |
| 51 |
Correct |
786 ms |
39912 KB |
Output is correct |
| 52 |
Correct |
500 ms |
39672 KB |
Output is correct |
| 53 |
Correct |
1251 ms |
31480 KB |
Output is correct |
| 54 |
Correct |
577 ms |
31736 KB |
Output is correct |
| 55 |
Correct |
932 ms |
30816 KB |
Output is correct |
| 56 |
Correct |
710 ms |
34680 KB |
Output is correct |
| 57 |
Correct |
877 ms |
30812 KB |
Output is correct |
| 58 |
Correct |
916 ms |
31316 KB |
Output is correct |
| 59 |
Correct |
189 ms |
35064 KB |
Output is correct |
