#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
int s, e;
ll gc;
node *lc, *rc;
node(int S, int E) {
s = S, e = E, gc = 0;
lc = rc = NULL;
}
void update(int &p, ll &K)
{
if(p < s || e <= p) return;
if(e - s == 1) {
gc = K;
return;
}
int mid = (s + e) / 2;
if(lc == NULL and p < mid)
lc = new node(s, mid);
else if(rc == NULL and mid <= p)
rc = new node(mid, e);
gc = 0;
if(lc != NULL)
lc -> update(p, K), gc = gcd(gc, lc -> gc);
if(rc != NULL)
rc -> update(p, K), gc = gcd(gc, rc -> gc);
}
ll get(int &l, int &r)
{
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return gc;
ll g = 0;
if(lc != NULL) g = gcd(g, lc -> get(l, r));
if(rc != NULL) g = gcd(g, rc -> get(l, r));
return g;
}
};
int sz;
struct Segnode
{
int s, e;
node *tree;
Segnode *lc, *rc;
Segnode(int S, int E) {
s = S, e = E;
lc = rc = NULL;
tree = new node(0, sz);
}
void update(int &p, int &p2, ll &K)
{
if(p < s || e <= p) return;
if(e - s == 1){
tree->update(p2, K);
return;
}
int mid = (s + e) / 2;
if(lc == NULL and p < mid)
lc = new Segnode(s, mid);
if(rc == NULL and p >= mid)
rc = new Segnode(mid, e);
if(lc != NULL)
lc -> update(p, p2, K);
if(rc != NULL)
rc -> update(p, p2, K);
int p21 = p2 + 1;
ll g1 = 0;
if(lc != NULL) g1 = lc -> tree -> get(p2, p21);
ll g2 = 0;
if(rc != NULL) g2 = rc -> tree -> get(p2, p21);
g1 = gcd(g1, g2);
tree -> update(p2, g1);
}
ll get(int &lx, int &rx, int &ly, int &ry)
{
if(rx <= s || e <= lx) return 0;
if(lx <= s && e <= rx)
return tree->get(ly, ry);
ll g = 0;
if(lc != NULL)
g = lc -> get(lx, rx, ly, ry);
if(rc != NULL)
g = gcd(g, rc -> get(lx, ly, rx, ry));
return g;
}
};
Segnode* tree;
void init(int R, int C)
{
sz = C;
tree = new Segnode(0, R);
}
void update(int p, int q, ll K)
{
tree->update(p, q, K);
}
ll calculate(int lx, int ly, int rx, int ry)
{
rx ++ , ry++;
return tree->get(lx, rx, ly, ry);
}
/*
#define MAX_SIZE 1000000000
#define MAX_N 272000
int main() {
int R, C, N;
int P, Q, U, V;
long long K;
int i, type;
assert(scanf("%d", &R) == 1);
assert(scanf("%d", &C) == 1);
assert(scanf("%d", &N) == 1);
init(R, C);
std::vector<long long> answers;
for (i = 0; i < N; i++) {
assert(scanf("%d", &type) == 1);
if (type == 1) {
assert(scanf("%d%d%lld", &P, &Q, &K) == 3);
update(P, Q, K);
} else if (type == 2) {
assert(scanf("%d%d%d%d", &P, &Q, &U, &V) == 4);
answers.push_back(calculate(P, Q, U, V));
}
}
for (auto answer: answers) {
printf("%lld\n", answer);
}
return 0;
}
//*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |