| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1088472 |
2024-09-14T13:26:32 Z |
makrav |
Game (IOI13_game) |
C++14 |
|
0 ms |
0 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int 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 pair<int, int> {
// int x, y;
// };
bool operator<(pair<int, int> x, pair<int, int> y) {
return (x.second == y.second ? x.first < y.first : x.second < y.second);
}
bool operator==(pair<int, int> x, pair<int, int> y) {
return x.first == y.first && x.second == y.second;
}
bool operator>(pair<int, int> x, pair<int, int> y) {
if (x == y) return false;
return !(x < y);
}
bool compare(pair<int, int> x, pair<int, int> y) {
return (x.first == y.first ? x.second < y.second : x.first < y.first);
}
bool cmp(pair<pair<int, int>, int> c1, pair<pair<int, int>, int> c2) {
if (c1.first == c2.first) return c1.second < c2.second;
return compare(c1.first, c2.first);
}
struct segtree {
int n;
vector<int> a;
vector<pair<int, int>> C;
vector<int> t;
segtree() = default;
segtree(int n_, vector<pair<pair<int, int>, int>> A) {
n = n_;
a.resize(n); C.resize(n);
for (int i = 0; i < n; i++) {
C[i] = A[i].first; a[i] = A[i].second;
}
t.assign(4 * n, 0);
build(1, 0, n);
}
void build(int v, int tl, int tr) {
if (tl + 1 == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
t[v] = gcd(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int tl, int tr, pair<int, int> &c, int newval) {
if (tl + 1 == tr) {
t[v] = newval;
return;
}
int tm = (tl + tr) / 2;
if (C[tm - 1] < c) upd(v * 2 + 1, tm, tr, c, newval);
else upd(v * 2, tl, tm, c, newval);
t[v] = gcd(t[v * 2], t[v * 2 + 1]);
}
int get(int v, int tl, int tr, int y1, int y2) {
if (y1 <= C[tl].second && C[tr - 1].second <= y2) return t[v];
if (C[tl].second > y2 || C[tr - 1].second < y1) return 0;
int tm = (tl + tr) / 2;
return gcd(get(v*2,tl,tm,y1,y2), get(v*2+1,tm,tr,y1,y2));
}
};
struct merge_sort_tree {
int n;
vector<pair<pair<int, int>, int>> xd;
vector<segtree> sg;
vector<vector<pair<pair<int, int>, int>>> tree;
merge_sort_tree() = default;
merge_sort_tree(int n_, vector<pair<pair<int, int>, int>> &xd_) {
xd =xd_;
sort(all(xd), cmp);
n = n_;
tree.resize(4 * n);
sg.resize(4 * n);
build(1, 0, n);
}
void build(int v, int tl, int tr) {
if (tl + 1 == tr) {
tree[v] = {xd[tl]};
sg[v] = segtree(tr - tl, tree[v]);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
tree[v].resize(tr - tl);
merge(all(tree[v * 2]), all(tree[v * 2 + 1]), tree[v].begin());
sg[v] = segtree(tr - tl, tree[v]);
}
void update_value(int v, int tl, int tr, pair<int, int> x, int value) {
sg[v].upd(1, 0, tr - tl, x, value);
if (tl + 1 == tr) return;
int tm = (tl + tr) / 2;
if (compare(xd[tm - 1].first, x)) update_value(v * 2 + 1, tm, tr, x, value);
else update_value(v * 2, tl, tm, x, value);
}
int getans(int v, int tl, int tr, int xl, int xr, int yl, int yr) {
if (xl > xd[tr - 1].first.first || xr < xd[tl].first.first) return 0;
if (xl <= xd[tl].first.first && xd[tr - 1].first.first <= xr) {
return sg[v].get(1, 0, tr - tl, yl, yr);
}
int tm = (tl + tr) / 2;
return gcd(getans(v * 2, tl, tm, xl, xr, yl, yr), getans(v * 2 + 1, tm, tr, xl, xr, yl, yr));
}
};
map<pair<int, int>, int> value, firocc;
const int K = 1000000000;
int curind_query = 0, lol = -1;
vector<pair<int, int>> ahaha;
merge_sort_tree mst;
int mst_size = 0;
void init(int32_t R, int32_t C) {
/* ... */
}
void update(int32_t P, int32_t Q, long long kk) {
// curind_query++;
// if (firocc.find({P, Q}) == firocc.end()) {
// firocc[{P, Q}] = curind_query;
// }
value[{P, Q}] = kk;
ahaha.pb({P, Q});
return;
if (curind_query % K == 0) {
vector<pair<pair<int, int>, int>> to_mst;
for (auto &u : value) to_mst.pb(u);
mst_size = sz(to_mst);
mst = merge_sort_tree(mst_size, to_mst);
ahaha.clear();
} else {
if (firocc[{P, Q}] <= curind_query - curind_query % K) {
mst.update_value(1, 0, mst_size, {P, Q}, kk);
} else {
ahaha.pb({P, Q});
}
}
}
long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
int ans1 = 0; //(mst_size == 0 ? 0 : mst.getans(1, 0, mst_size, P, U, Q, V));
for (auto &u : ahaha) {
if (P <= u.first && u.first <= U && Q <= u.second && u.second <= V) {
ans1 = gcd2(ans1, value[u]);
}
}
return ans1;
}
#ifdef LOCAL
signed main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int r, c, n; cin >> r >> c >> n;
init(r, c);
for (int i = 0; i < n; i++) {
int t; cin >> t;
if (t == 1) {
int p, q, k; cin >> p >> q >> k; update(p, q, k);
} else {
int p, q, u, v; cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << '\n';
}
}
}
#endif
Compilation message
game.cpp: In member function 'void segtree::build(ll, ll, ll)':
game.cpp:71:16: error: 'gcd' was not declared in this scope; did you mean 'gcd2'?
71 | t[v] = gcd(t[v * 2], t[v * 2 + 1]);
| ^~~
| gcd2
game.cpp: In member function 'void segtree::upd(ll, ll, ll, std::pair<long long int, long long int>&, ll)':
game.cpp:82:16: error: 'gcd' was not declared in this scope; did you mean 'gcd2'?
82 | t[v] = gcd(t[v * 2], t[v * 2 + 1]);
| ^~~
| gcd2
game.cpp: In member function 'll segtree::get(ll, ll, ll, ll, ll)':
game.cpp:89:16: error: 'gcd' was not declared in this scope; did you mean 'gcd2'?
89 | return gcd(get(v*2,tl,tm,y1,y2), get(v*2+1,tm,tr,y1,y2));
| ^~~
| gcd2
game.cpp: In member function 'll merge_sort_tree::getans(ll, ll, ll, ll, ll, ll, ll)':
game.cpp:135:16: error: 'gcd' was not declared in this scope; did you mean 'gcd2'?
135 | return gcd(getans(v * 2, tl, tm, xl, xr, yl, yr), getans(v * 2 + 1, tm, tr, xl, xr, yl, yr));
| ^~~
| gcd2
