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 "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
#define F first
#define S second
typedef vector<ii> vii;
typedef vector<vii> vvii;
long long gcd2(long long X, long long Y) {
//cout << X << ' ' << Y << ": ";
long long tmp;
if (X < Y) swap(X,Y);
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
//cout << X << endl;
return X;
}
class SegmentTree {
private:
ll n;
vi data;
vector<long long int> st;
ll left (ll x){
return (x << 1);
}
ll right(ll x){
return ((x << 1) + 1);
}
void build (ll i, ll l, ll r){
if (l == r){
st[i] = data[l];
}else{
ll m = (l+r)/2;
build(left(i),l,m);
build(right(i),m+1,r);
st[i] = gcd2(st[left(i)], st[right(i)]);
}
}
long long int query (ll i, ll l, ll r, ll ql, ll qr){
if (qr >= r && l >= ql){
return st[i];
}else if (ql > r || l > qr){
return 0;
}else{
ll m = (l+r)/2;
long long int ansl = query(left(i),l,m,ql,qr);
long long int ansr = query(right(i),m+1,r,ql,qr);
return gcd2(ansl,ansr);
}
}
void update (ll i, ll l, ll r, ll idx, long long int val){
if (l == idx && r == idx){
st[i] = val;
}else if (r >= idx && idx >= l){
ll m = (l+r)/2;
update(left(i),l,m,idx,val);
update(right(i),m+1,r,idx,val);
st[i] = gcd2(st[left(i)], st[right(i)]);
}
}
public:
SegmentTree (const vi& _data): data(_data), n(_data.size()){
st.assign(4*n,0);
//build(1,0,n-1);
}
void update (ll idx, long long int val){
update(1,0,n-1,idx,val);
}
long long int query (ll ql, ll qr){
return query(1,0,n-1,ql,qr);
}
void print(){
for (auto i: st){ cout << i << ' '; }
cout << endl;
}
};
vector<SegmentTree> grid;
void init(int r, int c) {
/* ... */
vi te;
te.assign(c,0);
grid.assign(r,SegmentTree(te));
}
void update(int p, int q, long long k) {
/* ... */
grid[p].update(q,k);
}
long long calculate(int p, int q, int u, int v) {
/* ... */
long long int ans = 0;
for (ll i = p; u >= i; i++){
//cout << "grid[i].query(q,v): " << ' ';
//cout << grid[i].query(q,v) << endl;
ans = gcd2(ans,grid[i].query(q,v));
}
return ans;
}
Compilation message (stderr)
game.cpp: In constructor 'SegmentTree::SegmentTree(const vi&)':
game.cpp:29:8: warning: 'SegmentTree::data' will be initialized after [-Wreorder]
29 | vi data;
| ^~~~
game.cpp:28:8: warning: 'll SegmentTree::n' [-Wreorder]
28 | ll n;
| ^
game.cpp:71:5: warning: when initialized here [-Wreorder]
71 | SegmentTree (const vi& _data): data(_data), n(_data.size()){
| ^~~~~~~~~~~
# | 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... |