| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29107 |
2017-07-18T09:19:56 Z |
nibnalin |
Game (IOI13_game) |
C++14 |
|
0 ms |
2420 KB |
#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
using namespace std;
typedef long long lli;
struct ppnode0 {
lli ans;
ppnode0 *l, *r;
ppnode0(lli _res = 0ll, ppnode0 *_l = NULL, ppnode0 *_r = NULL)
{
ans = _res, l = _l, r = _r;
}
};
struct ppnode1 {
ppnode0* ans;
ppnode1 *l, *r;
ppnode1(ppnode0* _res = new ppnode0(), ppnode1 *_l = NULL, ppnode1 *_r = NULL)
{
ans = _res, l = _l, r = _r;
}
};
typedef ppnode0* pnode0;
typedef ppnode1* pnode1;
pair<lli, lli> sz;
pnode1 grid;
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;
}
pnode0 upd0(pnode0 root, lli L, lli R, lli b, lli v)
{
if(!root) root = new ppnode0();
if(L == R) return new ppnode0(v, NULL, NULL);
else
{
pnode0 nw = new ppnode0(gcd2(root->ans, v), NULL, NULL);
if(b <= (L+R)/2) nw->l = upd0(root->l, L, (L+R)/2, b, v), nw->r = root->r;
else nw->r = upd0(root->r, (L+R)/2+1, R, b, v), nw->l = root->l;
return nw;
}
}
pnode1 upd1(pnode1 root, lli L, lli R, lli a, lli b, lli v)
{
if(!root) root = new ppnode1();
if(L == R) return new ppnode1(upd0(root->ans, 0, sz.second, b, v), NULL, NULL);
else
{
pnode1 nw = new ppnode1(upd0(root->ans, 0, sz.second, b, v), NULL, NULL);
if(a <= (L+R)/2) nw->l = upd1(root->l, L, (L+R)/2, a, b, v), nw->r = root->r;
else nw->r = upd1(root->r, (L+R)/2+1, R, a, b, v), nw->l = root->l;
return nw;
}
}
lli qry0(pnode0 root, lli L, lli R, lli a, lli b)
{
if(a > R || b < L || !root) return 0ll;
else if(a <= L && R <= b) return root->ans;
else return gcd2(qry0(root->l, L, (L+R)/2, a, b), qry0(root->r, (L+R)/2+1, R, a, b));
}
lli qry1(pnode1 root, lli L, lli R, lli a, lli b, lli c, lli d)
{
if(a > R || b < L || !root) return 0ll;
else if(a <= L && R <= b) return qry0(root->ans, 0, sz.second, c, d);
else return gcd2(qry1(root->l, L, (L+R)/2, a, b, c, d), qry1(root->r, (L+R)/2+1, R, a, b, c, d));
}
void init(int _R, int _C) {
sz.first = _R-1, sz.second = _C-1;
grid = NULL;
}
void update(int P, int Q, long long K) {
//cout << "upd\n";
grid = upd1(grid, 0, sz.first, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
//cout << "calc\n";
return qry1(grid, 0, sz.first, min(P, U), max(P, U), min(Q, V), max(Q, V));
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2420 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2420 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2420 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2420 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
