This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "grader.h"
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e4 + 20;
const int maxb = 15;
const int sq = 100;
int sz;
int x[maxn] , y[maxn] , tmp[maxn] , seg[maxb][maxn] , where[maxb][maxn];
ll g[maxb][maxn * 4] , val[maxn];
vector<int> cmpx;
map<pair<int , int> , int> MP;
bool cmpy(int a , int b)
{
return y[a] < y[b];
}
void build(int s = 0 , int e = cmpx.size() , int h = 0)
{
if(e - s < 2)
{
seg[h][s] = tmp[s];
where[h][tmp[s]] = s;
return;
}
int m = (s + e) / 2;
build(s , m , h + 1);
build(m , e , h + 1);
merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s , cmpy);
for(int i = s; i < e; i++)
where[h][seg[h][i]] = i;
}
void buildgcd(int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
if(e - s < 2)
{
g[h][v] = val[seg[h][s]];
return;
}
int m = (s + e) / 2;
buildgcd(h , s , m , 2 * v);
buildgcd(h , m , e , 2 * v + 1);
g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}
void updategcd(int p , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
if(e - s < 2)
{
g[h][v] = val[seg[h][s]];
return;
}
int m = (s + e) / 2;
if(p < m)
updategcd(p , h , s , m , 2 * v);
else
updategcd(p , h , m , e , 2 * v + 1);
g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}
ll getGcd(int l , int r , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
if(l <= s && e <= r)
return g[h][v];
if(r <= s || e <= l)
return 0;
int m = (s + e) / 2;
return __gcd(getGcd(l , r , h , s , m , 2 * v) , getGcd(l , r , h , m , e , 2 * v + 1));
}
ll get(int l , int r , int l2 , int r2 , int s = 0 , int e = cmpx.size() , int h = 0)
{
if(l <= s && e <= r)
{
y[maxn - 1] = l2; l2 = lower_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
y[maxn - 1] = r2; r2 = upper_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
return getGcd(l2 , r2 , h);
}
if(r <= s || e <= l)
return 0;
int m = (s + e) / 2;
return __gcd(get(l , r , l2 , r2 , s , m , h + 1) , get(l , r , l2 , r2 , m , e , h + 1));
}
void rebuild()
{
memset(where , -1 , sizeof where);
cmpx.clear();
for(int i = 0; i < sz; i++)
cmpx.pb(x[i]);
sort(cmpx.begin() , cmpx.end());
map<int , int> mp;
for(int i = 0; i < sz; i++)
{
int p = lower_bound(cmpx.begin() , cmpx.end() , x[i]) - cmpx.begin();
p += mp[x[i]];
mp[x[i]]++;
tmp[p] = i;
}
build();
for(int i = 0; i < maxb; i++)
buildgcd(i);
}
void init(int R, int C)
{
memset(where , -1 , sizeof where);
R = R , C = C;
}
void update(int P, int Q, long long K)
{
if(MP.count({P , Q}))
{
int ind = MP[make_pair(P , Q)];
val[ind] = K;
for(int i = 0; i < maxb; i++)
if(where[i][ind] != -1)
updategcd(where[i][ind] , i);
}
else
{
x[sz] = P , y[sz] = Q , val[sz] = K;
MP[make_pair(P , Q)] = sz;
sz++;
if(sz % sq == 0)
rebuild();
}
}
long long calculate(int l1, int l2, int r1, int r2)
{
ll res = 0;
for(int i = 0; i < sz; i++)
if(l1 <= x[i] && x[i] <= r1 && l2 <= y[i] && y[i] <= r2)
res = __gcd(res , val[i]);
int l = lower_bound(cmpx.begin() , cmpx.end() , l1) - cmpx.begin();
int r = upper_bound(cmpx.begin() , cmpx.end() , r1) - cmpx.begin();
return __gcd(res , get(l , r , l2 , r2));
}
Compilation message (stderr)
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
# | 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... |