#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
const int LG = 20;
ll gcd(ll a , ll b) { return a ? gcd(b % a , a) : b; }
struct rmq {
vector<ll> arr[LG], G;
inline rmq() {}
inline rmq(ll* L , ll* R) {
int sz = R - L;
G.resize(sz + 1);
int me = 0;
rep(i ,1 , sz + 1) {
G[i] = me;
if ((2 << me) == i) me++;
}
rep(i , 0 , LG)
arr[i].resize(sz);
rep(i , 0 , sz)
arr[0][i] = *(L + i);
rep(i , 1 , LG)
for (int j = 0, k = 1 << (i - 1); j < sz; j++, k++)
arr[i][j] = gcd(arr[i - 1][j] , k >= sz ? 0 : arr[i - 1][k]);
}
inline ll ask(int l , int r) {
if (l == r) return 0;
int sz = G[r - l];
return gcd(arr[sz][l] , arr[sz][r - (1 << sz)]);
}
};
const int sq = 200;
const int N = 22010 * 4;
int junk;
vector<pair<pii , ll>> a[N];
map<pii , ll> mp;
vector<int> b[N];
rmq ask[N];
ll tmp[N];
void build(int id) {
b[id].resize(a[id].size());
sort(all(a[id]));
iota(all(b[id]) , 0);
sort(all(b[id]) , [&id](int l , int r) { return a[id][l].first.second < a[id][r].first.second; });
rep(i , 0 , a[id].size())
tmp[i] = a[id][b[id][i]].second;
ask[id] = rmq(tmp , tmp + a[id].size());
}
void init(int R, int C) {
if (mp.size()) assert(0);
}
void update(int P, int Q, long long K) {
junk++;
pii me(P , Q);
if (mp.count(me)) {
for (int i = 0;;i++)
if (me <= a[i].back().first) {
for (auto &e : a[i])
if (e.first == me)
e.second = K;
build(i);
break;
}
}
else {
for (int i = 0;;i++)
if (a[i].empty() || me <= a[i].back().first) {
a[i].pb({me , K});
build(i);
break;
}
}
mp[me] = K;
if (junk % sq == 0) {
int cnt = 0;
int ptr = 0;
a[0].clear();
for (auto e : mp) {
a[ptr].pb(e);
cnt++;
if (cnt % sq == 0) {
cnt = 0;
ptr++;
a[ptr].clear();
}
}
rep(i , ptr + 1, ptr + sq + 10) a[i].clear();
rep(i , 0 , ptr + 10)
build(i);
}
}
long long calculate(int P, int Q, int U, int V) {
ll res = 0;
int go = 0;
for(;;go++) {
if (a[go].empty()) return 0;
if (P <= a[go].back().first.first) {
for (auto e : a[go])
if (e.first.first >= P && e.first.first <= U && e.first.second >= Q && e.first.second <= V)
res = gcd(res , e.second);
break;
}
}
go++;
for (;;go++) {
if (a[go].empty()) return res;
if (U < a[go].back().first.first) {
for (auto e : a[go])
if (e.first.first >= P && e.first.first <= U && e.first.second >= Q && e.first.second <= V)
res = gcd(res , e.second);
return res;
}
int l = lower_bound(all(b[go]) , Q , [&go](int l , int r) { return a[go][l].first.second < r; }) - b[go].begin();
int r = upper_bound(all(b[go]) , V , [&go](int l , int r) { return l < a[go][r].first.second; }) - b[go].begin();
res = gcd(res , ask[go].ask(l , r));
}
return -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;
^~~
game.cpp:2:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
