| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 609863 |
2022-07-28T02:18:50 Z |
jairRS |
Horses (IOI15_horses) |
C++17 |
|
579 ms |
54204 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 500000;
const ll MOD = 1000000000LL + 7LL;
ll gN, gX[MAXN], gY[MAXN];
struct bignum{
ll val = 0;
bool overMOD = false;
bignum(ll _val){
overMOD = _val/MOD > 0;
val = _val % MOD;
}
void scale(ll x){
bignum newBignum = bignum(val * x);
overMOD |= newBignum.overMOD;
val = newBignum.val;
}
bignum operator*(const bignum &a) const {
bignum res(val*a.val);
res.overMOD |= overMOD | a.overMOD;
return res;
}
};
struct node{
ll soldY = 0;
bignum XBlue = bignum(1);
bignum XRed = bignum(1);
};
//1-based
struct segmentTree{
vector<node> tree;
int treeSize, power2 = 1;
segmentTree(int size){
while(power2 < size)
power2 *= 2;
treeSize = 2*power2 - 1;
tree = vector<node>(treeSize + 1);
}
node merge(const node &a, const node &b){
if(b.soldY == 0)
return a;
bignum XProduct = a.XRed * b.XBlue;
XProduct.scale(b.soldY);
node res = a;
if(!XProduct.overMOD && a.soldY > XProduct.val){
res = a;
res.XRed = a.XRed * b.XBlue * b.XRed;
} else {
res = b;
res.XBlue = a.XRed * b.XBlue * a.XBlue;
}
return res;
}
//i is 1-based
void update(int i){
int in = i + treeSize/2;
tree[in].soldY = gY[i - 1];
tree[in].XBlue = gX[i - 1];
in /= 2;
while(in > 0){
tree[in] = merge(tree[in*2], tree[in*2 + 1]);
in /= 2;
}
}
node query(int ql, int qr){
return query(1, power2, ql, qr);
}
node query(int l, int r, int ql, int qr, int i = 1){
if(l > qr || r < ql)
return node();
if(ql <= l && r <= qr)
return tree[i];
int mid = (l + r)/2;
node q1 = query(l, mid, ql, qr, i*2);
node q2 = query(mid + 1, r, ql, qr, i*2 + 1);
return merge(q1, q2);
}
};
segmentTree segTree(1);
int getAns(){
node ans = segTree.query(1, gN);
ans.XBlue.scale(ans.soldY);
return ans.XBlue.val;
}
int init(int N, int X[], int Y[]) {
gN = N;
for (int i = 0; i < N; i++)
{
gX[i] = X[i];
gY[i] = Y[i];
}
segTree = segmentTree(N);
for (int i = 0; i < N; i++)
segTree.update(i + 1);
/*
for (int i = 1; i <= 7; i++)
{
node cur = segTree.tree[i];
cerr << i << ": "
<< cur.soldY << " "
<< cur.XBlue.val << " "
<< cur.XRed.val << endl;
}
*/
return getAns();
}
int updateX(int pos, int val) {
gX[pos] = val;
segTree.update(pos + 1);
return getAns();
}
int updateY(int pos, int val) {
gY[pos] = val;
segTree.update(pos + 1);
return getAns();
}
Compilation message
horses.cpp: In function 'int getAns()':
horses.cpp:97:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
97 | node ans = segTree.query(1, gN);
| ^~
horses.cpp:99:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
99 | return ans.XBlue.val;
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
2 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
492 ms |
53960 KB |
Output is correct |
| 2 |
Correct |
575 ms |
54036 KB |
Output is correct |
| 3 |
Correct |
531 ms |
54044 KB |
Output is correct |
| 4 |
Correct |
539 ms |
54020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Correct |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
428 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
340 KB |
Output is correct |
| 29 |
Correct |
2 ms |
340 KB |
Output is correct |
| 30 |
Correct |
2 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
399 ms |
53152 KB |
Output is correct |
| 34 |
Correct |
436 ms |
53080 KB |
Output is correct |
| 35 |
Correct |
400 ms |
53152 KB |
Output is correct |
| 36 |
Correct |
426 ms |
53084 KB |
Output is correct |
| 37 |
Correct |
394 ms |
53080 KB |
Output is correct |
| 38 |
Correct |
393 ms |
53124 KB |
Output is correct |
| 39 |
Correct |
395 ms |
53088 KB |
Output is correct |
| 40 |
Correct |
392 ms |
53080 KB |
Output is correct |
| 41 |
Correct |
377 ms |
53068 KB |
Output is correct |
| 42 |
Correct |
385 ms |
53080 KB |
Output is correct |
| 43 |
Correct |
401 ms |
53088 KB |
Output is correct |
| 44 |
Correct |
376 ms |
53108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
0 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
2 ms |
340 KB |
Output is correct |
| 24 |
Correct |
2 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
3 ms |
340 KB |
Output is correct |
| 27 |
Correct |
2 ms |
340 KB |
Output is correct |
| 28 |
Correct |
2 ms |
428 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
2 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
502 ms |
54004 KB |
Output is correct |
| 34 |
Correct |
570 ms |
53992 KB |
Output is correct |
| 35 |
Correct |
536 ms |
53964 KB |
Output is correct |
| 36 |
Correct |
548 ms |
53996 KB |
Output is correct |
| 37 |
Correct |
417 ms |
53084 KB |
Output is correct |
| 38 |
Correct |
400 ms |
53084 KB |
Output is correct |
| 39 |
Correct |
425 ms |
53088 KB |
Output is correct |
| 40 |
Correct |
422 ms |
53076 KB |
Output is correct |
| 41 |
Correct |
401 ms |
53080 KB |
Output is correct |
| 42 |
Correct |
401 ms |
53080 KB |
Output is correct |
| 43 |
Correct |
391 ms |
53088 KB |
Output is correct |
| 44 |
Correct |
400 ms |
53080 KB |
Output is correct |
| 45 |
Correct |
392 ms |
53084 KB |
Output is correct |
| 46 |
Correct |
396 ms |
53096 KB |
Output is correct |
| 47 |
Correct |
393 ms |
53088 KB |
Output is correct |
| 48 |
Correct |
383 ms |
53084 KB |
Output is correct |
| 49 |
Correct |
579 ms |
54048 KB |
Output is correct |
| 50 |
Correct |
562 ms |
54060 KB |
Output is correct |
| 51 |
Correct |
533 ms |
54004 KB |
Output is correct |
| 52 |
Correct |
529 ms |
54084 KB |
Output is correct |
| 53 |
Correct |
547 ms |
54008 KB |
Output is correct |
| 54 |
Correct |
523 ms |
53864 KB |
Output is correct |
| 55 |
Correct |
509 ms |
53276 KB |
Output is correct |
| 56 |
Correct |
513 ms |
53996 KB |
Output is correct |
| 57 |
Correct |
504 ms |
54016 KB |
Output is correct |
| 58 |
Correct |
496 ms |
54204 KB |
Output is correct |
| 59 |
Correct |
388 ms |
53080 KB |
Output is correct |
