| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136854 |
2019-07-26T11:12:20 Z |
Juney |
Game (IOI13_game) |
C++14 |
|
15 ms |
10748 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; ll val;
CNODE() : l(0), r(0), val(0) {}
};
vector<CNODE> CT;
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.size(), CT.push_back(CNODE());
update(y, val, l, mid , CT[n].l);
}
else {
if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE());
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.size(), CT.push_back(CNODE());
return croot;
}
RNODE() : l(0), r(0), croot(0) {}
};
int rt_sz = 1;
RNODE RT[QUERY_SIZE * 40];
struct RDST {
void mrg(int y, int n, int ln, int rn, int l=1, int r=MAX_RANGE) {
if(ln == 0 && rn == 0) return;
CT[n].val = gcd(CT[ln].val, CT[rn].val);
if(l == r) return;
int mid = (l + r) >> 1;
if(y <= mid) {
if(CT[n].l == 0) CT[n].l = CT.size(), CT.push_back(CNODE());
mrg(y, CT[n].l, CT[ln].l, CT[rn].l, l, mid);
}
else {
if(CT[n].r == 0) CT[n].r = CT.size(), CT.push_back(CNODE());
mrg(y, CT[n].r, CT[ln].r, CT[rn].r, mid+1, r);
}
}
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);
}
mrg(y, RT[n].get_root(), RT[RT[n].l].get_root(), RT[RT[n].r].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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
10616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
