| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136957 |
2019-07-26T16:38:03 Z |
Juney |
Game (IOI13_game) |
C++14 |
|
239 ms |
256004 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_RANGE 1000000000
#define QUERY_SIZE 22000
#define gcd(x, y) gcd2(x, y)
typedef long long ll;
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 CNODE {
int l, r, data; ll val;
CNODE() : l(0), r(0), val(0), data(-1) {}
};
int ct_sz = 1;
CNODE CT[QUERY_SIZE * 700];
struct CDST {
void update(int y, ll val, int l, int r, int n) {
if(l == r) {
CT[n].val = val;
return;
}
int mid = (l + r) >> 1;
if(y <= mid) {
if(CT[n].l == 0) CT[n].l = ++ct_sz;
update(y, val, l, mid , CT[n].l);
}
else {
if(CT[n].r == 0) CT[n].r = ++ct_sz;
update(y, val, mid+1, r, CT[n].r);
}
CT[n].val = gcd(CT[CT[n].l].val, CT[CT[n].r].val);
}
void update(int y, ll val, int n) { update(y, val, 1, MAX_RANGE, n); }
ll query(int c1, int c2, int l, int r, int n) {
if(n == 0 || r < c1 || c2 < l) return 0;
if(c1 <= l && r <= c2) return CT[n].val;
int mid = (l + r) >> 1;
return gcd(query(c1, c2, l, mid, CT[n].l), query(c1, c2, mid+1, r, CT[n].r));
}
ll query(int c1, int c2, int n) { return query(c1, c2, 1, MAX_RANGE, n); }
} cdst;
struct RNODE {
int l, r, croot;
int get_root() {
if(croot == 0) croot = ++ct_sz;
return croot;
}
RNODE() : l(0), r(0), croot(0) {}
};
int rt_sz = 1;
RNODE RT[QUERY_SIZE * 33];
struct RDST {
void update(int x, int y, ll val, int l=1, int r=MAX_RANGE, int n=1) {
if(l == r) {
cdst.update(y, val, RT[n].get_root());
return;
}
int mid = (l + r) >> 1;
if(x <= mid) {
if(RT[n].l == 0) RT[n].l = ++rt_sz;
update(x, y, val, l, mid, RT[n].l);
}
else {
if(RT[n].r == 0) RT[n].r = ++rt_sz;
update(x, y, val, mid+1, r, RT[n].r);
}
ll nval = gcd(cdst.query(y, y, RT[RT[n].l].get_root()), cdst.query(y, y, RT[RT[n].r].get_root()));
cdst.update(y, nval, RT[n].get_root());
}
ll query(int r1, int c1, int r2, int c2, int l=1, int r=MAX_RANGE, int n=1) {
if(n == 0 || r < r1 || r2 < l) return 0;
if(r1 <= l && r <= r2) return cdst.query(c1, c2, RT[n].get_root());
int mid = (l + r) >> 1;
return gcd(query(r1, c1, r2, c2, l, mid, RT[n].l), query(r1, c1, r2, c2, mid+1, r, RT[n].r));
}
} dst;
void init(int R, int C) {
/* ... */
}
void update(int P, int Q, long long K) {
dst.update(P+1, Q+1, K);
}
long long calculate(int P, int Q, int U, int V) {
return dst.query(P+1, Q+1, U+1, V+1);
}
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;
^~~
game.cpp: In constructor 'CNODE::CNODE()':
game.cpp:22:24: warning: 'CNODE::val' will be initialized after [-Wreorder]
int l, r, data; ll val;
^~~
game.cpp:22:15: warning: 'int CNODE::data' [-Wreorder]
int l, r, data; ll val;
^~~~
game.cpp:23:5: warning: when initialized here [-Wreorder]
CNODE() : l(0), r(0), val(0), data(-1) {}
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
239 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
208 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
233 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
208 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
210 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
