| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 396496 |
2021-04-30T04:41:50 Z |
phathnv |
Game (IOI13_game) |
C++11 |
|
13000 ms |
14856 KB |
#include <bits/stdc++.h>
#include "game.h"
typedef long long ll;
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Node{
int l, r;
ll data;
Node *Left, *Right;
Node(int _l, int _r){
l = _l;
r = _r;
data = 0;
Left = Right = nullptr;
}
ll get(int u, int v){
if (v < l || r < u || data == 0)
return 0;
if (u <= l && r <= v)
return data;
ll res = 0;
if (Left != nullptr)
res = gcd2(res, Left->get(u, v));
if (Right != nullptr)
res = gcd2(res, Right->get(u, v));
return res;
}
void update(int pos, ll val){
if (pos < l || r < pos)
return;
if (l == r){
data = val;
return;
}
int mid = (l + r) >> 1;
if (Left == nullptr)
Left = new Node(l, mid);
Left->update(pos, val);
if (Right == nullptr)
Right = new Node(mid + 1, r);
Right->update(pos, val);
data = gcd2(Left->data, Right->data);
}
};
Node* root[100];
void init(int r, int c) {
for(int i = 0; i < r; i++)
root[i] = new Node(0, c - 1);
}
void update(int p, int q, long long k) {
root[p]->update(q, k);
}
long long calculate(int x, int y, int u, int v) {
ll res = 0;
for(int i = x; i <= u; i++){
res = gcd2(res, root[i]->get(y, v));
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
787 ms |
14844 KB |
Output is correct |
| 5 |
Correct |
484 ms |
14680 KB |
Output is correct |
| 6 |
Correct |
620 ms |
12416 KB |
Output is correct |
| 7 |
Correct |
752 ms |
12036 KB |
Output is correct |
| 8 |
Correct |
464 ms |
9604 KB |
Output is correct |
| 9 |
Correct |
667 ms |
12140 KB |
Output is correct |
| 10 |
Correct |
608 ms |
11832 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Execution timed out |
13066 ms |
10200 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
780 ms |
14856 KB |
Output is correct |
| 13 |
Correct |
411 ms |
14612 KB |
Output is correct |
| 14 |
Correct |
618 ms |
12400 KB |
Output is correct |
| 15 |
Correct |
712 ms |
12148 KB |
Output is correct |
| 16 |
Correct |
458 ms |
9652 KB |
Output is correct |
| 17 |
Correct |
698 ms |
12300 KB |
Output is correct |
| 18 |
Correct |
659 ms |
11752 KB |
Output is correct |
| 19 |
Execution timed out |
13047 ms |
10324 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
808 ms |
14828 KB |
Output is correct |
| 13 |
Correct |
425 ms |
14692 KB |
Output is correct |
| 14 |
Correct |
608 ms |
12376 KB |
Output is correct |
| 15 |
Correct |
751 ms |
12352 KB |
Output is correct |
| 16 |
Correct |
471 ms |
9776 KB |
Output is correct |
| 17 |
Correct |
749 ms |
12204 KB |
Output is correct |
| 18 |
Correct |
622 ms |
11744 KB |
Output is correct |
| 19 |
Execution timed out |
13012 ms |
10472 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
