| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30600 |
2017-07-25T11:50:34 Z |
nibnalin |
Game (IOI13_game) |
C++14 |
|
0 ms |
2024 KB |
#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
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 ppnode0 {
int key, prior, self, v;
ppnode0 *l, *r;
ppnode0(int _key = 0, int _self = 0, int _v = 0, ppnode0*_l = NULL, ppnode0*_r = NULL)
{
key = _key, self = _self, v = _v, l = _l, r = _r;
prior = rand();
}
};
typedef ppnode0* pnode0;
inline int getv(pnode0 t)
{
return (t?t->v:0);
}
void upd(pnode0& t)
{
if(t)
{
t->v = t->self;
t->v = gcd2(t->v, gcd2(getv(t->l), getv(t->r)));
}
}
void split(pnode0 t, pnode0& L, pnode0& R, int k)
{
upd(t), upd(L), upd(R);
if(!t)
{
L = R = NULL;
return;
}
if(t->key <= k)
{
split(t->r, t->r, R, k);
L = t;
}
else
{
split(t->l, L, t->l, k);
R = t;
}
upd(t), upd(L), upd(R);
}
void merge(pnode0& t, pnode0 L, pnode0 R)
{
upd(t), upd(L), upd(R);
if(!L || !R)
{
t = (L?L:R);
return;
}
if(L->prior > R->prior)
{
merge(L->r, L->r, R);
t = L;
}
else
{
merge(R->l, L, R->l);
t = R;
}
upd(t), upd(L), upd(R);
}
/* int findval(pnode0& t, int k)
{
if(!t) return 0;
if(t->key == k) return t->self;
else if(t->key < k) return findval(t->r, k);
else return findval(t->l, k);
} */
struct ppnode1 {
pnode0 v;
ppnode1 *l, *r;
ppnode1(pnode0 _v = NULL, ppnode1* _l = NULL, ppnode1* _r = NULL)
{
v = _v, l = _l, r = _r;
}
};
typedef ppnode1* pnode1;
int qry0(pnode0& root, int a, int b)
{
if(!root) return 0;
pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
split(root, part1, part2, b);
split(part1, part3, part4, a-1);
int res = (part4?part4->v:0);
merge(part1, part3, part4);
merge(root, part1, part2);
return res;
}
int qry1(pnode1 root, int L, int R, int a, int b, int c, int d)
{
if(a > R || b < L || !root) return 0;
else if(a <= L && R <= b) return qry0(root->v, 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 upd0(pnode0& root, int idx, int v)
{
pnode0 part1 = NULL, part2 = NULL, part3 = NULL, part4 = NULL;
split(root, part1, part2, idx);
split(part1, part3, part4, idx-1);
part4 = new ppnode0(idx, v, v, NULL, NULL);
merge(part1, part3, part4);
merge(root, part1, part2);
}
void upd1(pnode1 root, int L, int R, int a, int b, int v)
{
if(L == R)
{
upd0(root->v, b, v);
}
else
{
if(a <= (L+R)/2)
{
if(!root->l) root->l = new ppnode1();
upd1(root->l, L, (L+R)/2, a, b, v);
}
else
{
if(!root->r) root->r = new ppnode1();
upd1(root->r, (L+R)/2+1, R, a, b, v);
}
int p = (root->l?qry0(root->l->v, b, b):0), q = (root->r?qry0(root->r->v, b, b):0);
upd0(root->v, b, gcd2(p, q));
}
//cout << L << " " << R << " " << root->v->v << "\n";
}
int r, c;
pnode1 grid;
void init(int _R, int _C)
{
//cout << "init\n";
r = _R-1;
c = _C-1;
grid = new ppnode1();
}
void update(int P, int Q, long long K)
{
//cout << "update\n";
upd1(grid, 0, r, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
//cout << "calculate\n";
return qry1(grid, 0, r, P, U, 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 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
