이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }
template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }
int MAXR, MAXC;
struct Seg1D {
Seg1D* c[2]{};
ll val = 0;
void modify(int l, int r, int i, long long k) {
if (l == r) {
val = k; return;
}
int m = (l + r) / 2;
if (i <= m) {
if (!c[0]) c[0] = new Seg1D();
c[0]->modify(l, m, i, k);
} else {
if (!c[1]) c[1] = new Seg1D();
c[1]->modify(m+1, r, i, k);
}
val = 0;
F(i, 0, 2) if (c[i]) val = gcd(val, c[i]->val);
}
ll query(int l, int r, int qxl, int qxr) {
ll res = 0;
if (qxr < l || r < qxl) return 0;
if (qxl <= l and r <= qxr) {
return val;
}
int m = (l + r) / 2;
if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr));
if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr));
return res;
}
};
struct Seg2D { // outer layer of segtrees
Seg2D* c[2]{};
Seg1D* repr = nullptr;
void modify(int l, int r, int x, int y, long long k) {
// log(n) segtree representations
if (!repr) repr = new Seg1D();
repr->modify(0, MAXC, y, k);
if (l == r) {
// cout << "NEW MODIFY AT " << l << " " << r << " : " << x << " "<< y << " FOR " << k << endl;
// cout << "YO.... " << repr->val << endl;
// cout << "ADDRESS OF THIS NODE: " << this << endl;
return;
}
int m = (l + r) / 2;
if (x <= m) {
if (!c[0]) c[0] = new Seg2D();
c[0]->modify(l, m, x, y, k);
} else {
if (!c[1]) c[1] = new Seg2D();
c[1]->modify(m+1, r, x, y, k);
}
}
ll query(int l, int r, int qxl, int qxr, pair<int, int> yrange) {
if (qxr < l || r < qxl) return 0;
// cout << "HAHA " << l << " " << r << " | " << qxl << " " << qxr << endl;
if (qxl <= l and r <= qxr) {
// cout << "HOW THE FUCK " << endl;
// cout << "ADDRESS OF THIS NODE: " << this << endl;
// cout << l << " " << r << " INCLUDED " << endl;
if (!repr) return 0;
// cout << "PULL FROM REPR " << endl;
return repr->query(0, MAXC, yrange.K, yrange.V);
}
ll res = 0;
int m = (l + r) / 2;
// cout << "AT " << l << " " << r << " SHOULD DEF HAVE " << c[0] << endl;
if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr, yrange));
if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr, yrange));
// cout << "WAT " << res << endl;
return res;
}
} root;
void init(int R, int C) {
MAXR = R-1, MAXC = C-1;
}
void update(int P, int Q, long long k) {
root.modify(0, MAXR, P, Q, k);
}
long long calculate(int p, int q, int u, int v) {
/* ... */
assert(p <= u and u <= MAXR);
assert(q <= v and v <= MAXC);
return root.query(0, MAXR, p, u, make_pair(q, v));
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |