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>
#define CNT (int)2e7
#define CNT2 (int)1e6
using namespace std;
const size_t MEMSIZE = 1e9 / 4; // in bytes
constexpr size_t MX_ALIGN = alignof(std::max_align_t);
char __attribute__((aligned(MX_ALIGN))) memory[MEMSIZE];
size_t memorypos;
void * operator new(size_t n){
if (memorypos + n >= MEMSIZE) {
memorypos = MEMSIZE / 3;
}
char *ret = memory + memorypos;
memorypos = size_t((memorypos+n+MX_ALIGN-1)&-MX_ALIGN);
return (void*)ret;
}
void operator delete(void *){}
void operator delete(void *, size_t){}
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 node{
int l = 0,r = 0;
long long val = 0;
};
vector<node> nodes(1);
int cnt = 1;
struct SegTree{
int root = -1;
void upd(int v,int tl,int tr,int pos,long long val){
if(tl == tr){
nodes[v].val = val;
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
if(nodes[v].l == 0)
nodes.push_back(new node());
nodes[v].l = cnt++;
upd(nodes[v].l,tl,tm,pos,val);
}
else{
if(nodes[v].r == 0)
nodes.push_back(new node());
nodes[v].r = cnt++;
upd(nodes[v].r,tm+1,tr,pos,val);
}
nodes[v].val = gcd2(nodes[nodes[v].l].val,nodes[nodes[v].r].val);
}
long long get(int v,int tl,int tr,int l,int r){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes[v].val;
}
int tm = (tl + tr)/2;
return gcd2(get(nodes[v].l,tl,tm,l,r),get(nodes[v].r,tm+1,tr,l,r));
}
void upd(int pos,long long val){
if(root == -1)
root = cnt++;
upd(root,1,1e9,pos,val);
}
long long get(int l,int r){
if(root == -1)
return 0;
return get(root,1,1e9,l,r);
}
};
map<int,int> mp;
int cntmp = 1;
SegTree numbers[22005];
struct node2{
int l = 0,r = 0;
SegTree val;
};
vector<node2>nodes(1);
int cnt2 = 1;
struct SegTree2D{
int root = -1;
void upd(int v,int tl,int tr,int x,int y,long long val){
nodes2[v].val.upd(y,numbers[mp[y]].get(tl,tr));
if(tl == tr){
return;
}
int tm = (tl + tr)/2;
if(x <= tm){
if(nodes2[v].l == 0)
nodes2.push_back(new node2());
nodes2[v].l = cnt2++;
upd(nodes2[v].l,tl,tm,x,y,val);
}
else{
if(nodes2[v].r == 0)
nodes2.push_back(new node2());
nodes2[v].r = cnt2++;
upd(nodes2[v].r,tm+1,tr,x,y,val);
}
}
long long get(int v,int tl,int tr,int l,int r,int l2,int r2){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes2[v].val.get(l2,r2);
}
int tm = (tl + tr)/2;
return gcd2(get(nodes2[v].l,tl,tm,l,r,l2,r2),get(nodes2[v].r,tm+1,tr,l,r,l2,r2));
}
void upd(int x,int y,long long val){
if(root == -1)
root = cnt2++;
upd(root,1,1e9,x,y,val);
}
long long get(int l,int r,int l2,int r2){
if(root == -1)
root = cnt2++;
return get(root,1,1e9,l,r,l2,r2);
}
}tree;
void init(int R, int C) {
//tree.init(R,C);
}
void update(int P, int Q, long long K) {
P++,Q++;
if(mp[Q] == 0){
mp[Q] = cntmp++;
}
numbers[mp[Q]].upd(P,K);
tree.upd(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++,Q++,U++,V++;
assert(cnt < CNT);
assert(cnt2 < CNT2);
return tree.get(P,U,Q,V);
}
Compilation message (stderr)
game.cpp: In member function 'void SegTree::upd(int, int, int, int, long long int)':
game.cpp:48:34: error: no matching function for call to 'std::vector<node>::push_back(node*)'
48 | nodes.push_back(new node());
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from game.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = node; _Alloc = std::allocator<node>; std::vector<_Tp, _Alloc>::value_type = node]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'node*' to 'const value_type&' {aka 'const node&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = node; _Alloc = std::allocator<node>; std::vector<_Tp, _Alloc>::value_type = node]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'node*' to 'std::vector<node>::value_type&&' {aka 'node&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
game.cpp:47:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
47 | if(nodes[v].l == 0)
| ^~
game.cpp:49:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
49 | nodes[v].l = cnt++;
| ^~~~~
game.cpp:54:34: error: no matching function for call to 'std::vector<node>::push_back(node*)'
54 | nodes.push_back(new node());
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from game.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = node; _Alloc = std::allocator<node>; std::vector<_Tp, _Alloc>::value_type = node]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'node*' to 'const value_type&' {aka 'const node&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = node; _Alloc = std::allocator<node>; std::vector<_Tp, _Alloc>::value_type = node]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'node*' to 'std::vector<node>::value_type&&' {aka 'node&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
game.cpp:53:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
53 | if(nodes[v].r == 0)
| ^~
game.cpp:55:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
55 | nodes[v].r = cnt++;
| ^~~~~
game.cpp: At global scope:
game.cpp:87:14: error: conflicting declaration 'std::vector<node2> nodes'
87 | vector<node2>nodes(1);
| ^~~~~
game.cpp:36:14: note: previous declaration as 'std::vector<node> nodes'
36 | vector<node> nodes(1);
| ^~~~~
game.cpp: In member function 'void SegTree2D::upd(int, int, int, int, int, long long int)':
game.cpp:92:5: error: 'nodes2' was not declared in this scope; did you mean 'node2'?
92 | nodes2[v].val.upd(y,numbers[mp[y]].get(tl,tr));
| ^~~~~~
| node2
game.cpp:98:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
98 | if(nodes2[v].l == 0)
| ^~
game.cpp:100:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
100 | nodes2[v].l = cnt2++;
| ^~~~~~
game.cpp:104:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
104 | if(nodes2[v].r == 0)
| ^~
game.cpp:106:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
106 | nodes2[v].r = cnt2++;
| ^~~~~~
game.cpp: In member function 'long long int SegTree2D::get(int, int, int, int, int, int, int)':
game.cpp:114:14: error: 'nodes2' was not declared in this scope; did you mean 'node2'?
114 | return nodes2[v].val.get(l2,r2);
| ^~~~~~
| node2
game.cpp:117:21: error: 'nodes2' was not declared in this scope; did you mean 'node2'?
117 | return gcd2(get(nodes2[v].l,tl,tm,l,r,l2,r2),get(nodes2[v].r,tm+1,tr,l,r,l2,r2));
| ^~~~~~
| node2