| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 97128 |
2019-02-14T03:27:56 Z |
E869120 |
Game (IOI13_game) |
C++14 |
|
4 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int cnts = 0;
long long gcd2(long long X, long long Y) {
if (Y == 0) return X;
return gcd2(Y, X % Y);
}
struct Node {
public:
long long val; int l, m, r;
};
class MeleeSegmentTree {
public:
vector<Node> dat; int size_;
void init(int I) {
size_ = 1;
while (size_ < I) size_ *= 3;
dat.push_back(Node{0LL, -1, -1});
}
void update_(unsigned int p, long long x, unsigned int cl, unsigned int cr, int u) {
if (cr - cl == 1) { dat[u].val = x; return; }
if (p * 3 < (cl + cl + cr)) {
if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
update_(p, x, cl, (cl + cl + cr) / 3, dat[u].l);
}
else if (p * 3 < (cl + cr + cr)) {
if (dat[u].m == -1) { dat[u].m = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, dat[u].m);
}
else {
if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
update_(p, x, (cl + cr + cr) / 3, cr, dat[u].r);
}
long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val;
long long e2 = 0; if (dat[u].m >= 0) e2 = dat[dat[u].m].val;
long long e3 = 0; if (dat[u].r >= 0) e3 = dat[dat[u].r].val;
dat[u].val = gcd2(e1, gcd2(e2, e3));
}
void update(int p, long long x) {
return update_((unsigned int)(p), x, 0, size_, 0);
}
long long query_(long long l, long long r, long long a, long long b, long long u) {
if (u == -1) return 0;
if (l <= a && b <= r) {
return dat[u].val;
}
if (r <= a || b <= l) return 0;
long long P1 = query_(l, r, a, (a + a + b) / 3, dat[u].l);
long long P2 = query_(l, r, (a + a + b) / 3, (a + b + b) / 3, dat[u].m);
long long P3 = query_(l, r, (a + b + b) / 3, b, dat[u].r);
return gcd2(P1, P2);
}
long long query(long long l, long long r) {
return query_(l, r, 0, size_, 0);
}
};
long long H, W;
struct Node2 {
MeleeSegmentTree val; int l, r;
};
class RangedSegmentTree {
public:
vector<Node2>dat; int size_, AX, AY, BX, BY; MeleeSegmentTree BASE;
void init(int I) {
BASE.init(W);
size_ = 1;
while (size_ < I) size_ *= 2;
dat.push_back(Node2{BASE, -1, -1});
}
void update_(int p, int q, long long x, int cl, int cr, int u) {
if (cr - cl == 1) {
//cout << "update " << u << " " << q << " " << x << endl;
dat[u].val.update(q, x); return;
}
if (p < ((cl + cr) >> 1)) {
if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node2{BASE, -1, -1}); }
update_(p, q, x, cl, (cl + cr) >> 1, dat[u].l);
}
else {
if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node2{BASE, -1, -1}); }
update_(p, q, x, (cl + cr) >> 1, cr, dat[u].r);
}
long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val.query(q, q+1);
long long e2 = 0; if (dat[u].r >= 0) e2 = dat[dat[u].r].val.query(q, q+1);
//cout << "update " << u << " " << q << " " << gcd2(e1, e2) << " " << e1 << " " << e2 << endl;
dat[u].val.update(q, gcd2(e1, e2));
}
void update(int p, int q, long long x) {
return update_(p, q, x, 0, size_, 0);
}
long long query_(int l, int r, int u) {
if (u == -1) return 0;
if (AX <= l && r <= BX) {
long long x = dat[u].val.query(AY, BY);
//cout << "query " << l << " " << r << " " << u << " " << x << endl;
return x;
}
if (r <= AX || BX <= l) return 0;
long long e1 = query_(l, (l + r) >> 1, dat[u].l);
long long e2 = query_((l + r) >> 1, r, dat[u].r);
return gcd2(e1, e2);
}
long long query(int ax, int ay, int bx, int by) {
bx++; by++;
AX = ax; AY = ay; BX = bx; BY = by;
return query_(0, size_, 0);
}
};
RangedSegmentTree X;
void init(int R, int C) {
H = R; W = C;
X.init(H);
}
void update(int P, int Q, long long K) {
X.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return X.query(P, Q, U, 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;
^~~
game.cpp: In member function 'long long int MeleeSegmentTree::query_(long long int, long long int, long long int, long long int, long long int)':
game.cpp:56:13: warning: unused variable 'P3' [-Wunused-variable]
long long P3 = query_(l, r, (a + b + b) / 3, b, dat[u].r);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
