| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 116803 |
2019-06-14T00:19:04 Z |
kig9981 |
Game (IOI13_game) |
C++17 |
|
0 ms |
0 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Seg
{
int l, r, s, e;
long long v;
Seg() : l(0), r(0), v(0), s(0), e(-1) {}
};
const int MAX=1e9;
vector<Seg> tree(2), tree2(1);
long long GCD(long long a, long long b)
{
for(;b;a%=b,swap(a,b));
return a;
}
long long get_gcd2(int n1, int n2, int p)
{
if(p==0 || n2<tree[p].s || tree[p].e<n1) return 0;
if(n1<=tree[p].s && tree[p].e<=n2) return tree2[p].v;
return GCD(get_gcd2(n1,n2,tree2[p].l),get_gcd2(n1,n2,tree2[p].r));
}
long long get_gcd(int x1, int x2, int y1, int y2, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(p==0 || x2<s || e<x1) return 0;
if(x1<=s && e<=x2) return get_gcd2(y1,y2,tree[p].v);
return GCD(get_gcd(x1,x2,y1,y2,tree[p].l,s,m),get_gcd(x1,x2,y1,y2,tree[p].r,m+1,e));
}
void set_tree2(int n, long long v, int p)
{
int s=0, e=MAX, sz=0;
static int S[33];
if(tree[p].s<tree[p].e) S[sz++]=p;
while(s<e) {
int m=(s+e)>>1;
if(tree[p].e==-1) break;
else if(tree[p].s==s && tree[p].e==e) {
if(n<=m) {
if(tree[p].l==0) tree[p].l=tsz++;
p=tree[p].l; e=m;
}
else {
if(tree[p].r==0) tree[p].r=tsz++;
p=tree[p].r; s=m+1;
}
if(tree[p].s<tree[p].e) S[sz++]=p;
}
else if(m<tree[p].s) {
if(n<=m) {
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
tree[tsz].v=tree[p].v;
tree[p].s=s; tree[p].e=e; tree[p].r=tsz; tree[p].l=++tsz;
S[sz++]=p; p=tsz++;
break;
}
s=m+1;
}
else {
if(n>m) {
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
tree[tsz].v=tree[p].v;
tree[p].s=s; tree[p].e=e; tree[p].l=tsz; tree[p].r=++tsz;
S[sz++]=p; p=tsz++;
break;
}
e=m;
}
}
if(tree[p].e==-1) tree[p].s=tree[p].e=n;
tree[p].v=v;
while(sz--) {
p=S[sz];
tree[p].v=GCD(tree[tree[p].l].v,tree[tree[p].r].v);
}
}
void set_tree(int x, int y, long long v, int p=1, int s=0, int e=MAX)
{
int m=(s+e)>>1;
if(tree[p].v==0) tree[p].v=tree2.size(), tree2.push_back(Seg());
if(s==e) {
set_tree2(y,v,tree[p].v);
return;
}
if(x<=m) {
if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].l,s,m);
}
else {
if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(Seg());
set_tree(x,y,v,tree[p].r,m+1,e);
}
set_tree2(y,GCD(get_gcd2(y,y,tree[tree[p].l].v),get_gcd2(y,y,tree[tree[p].r].v)),tree[p].v);
}
void init(int R, int C) {}
void update(int P, int Q, long long K) {set_tree(P,Q,K);}
long long calculate(int P, int Q, int U, int V) {return get_gcd(P,U,Q,V);}
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: In constructor 'Seg::Seg()':
game.cpp:9:12: warning: 'Seg::v' will be initialized after [-Wreorder]
long long v;
^
game.cpp:8:12: warning: 'int Seg::s' [-Wreorder]
int l, r, s, e;
^
game.cpp:10:2: warning: when initialized here [-Wreorder]
Seg() : l(0), r(0), v(0), s(0), e(-1) {}
^~~
game.cpp: In function 'void set_tree2(int, long long int, int)':
game.cpp:47:32: error: 'tsz' was not declared in this scope
if(tree[p].l==0) tree[p].l=tsz++;
^~~
game.cpp:47:32: note: suggested alternative: 'sz'
if(tree[p].l==0) tree[p].l=tsz++;
^~~
sz
game.cpp:51:32: error: 'tsz' was not declared in this scope
if(tree[p].r==0) tree[p].r=tsz++;
^~~
game.cpp:51:32: note: suggested alternative: 'sz'
if(tree[p].r==0) tree[p].r=tsz++;
^~~
sz
game.cpp:58:10: error: 'tsz' was not declared in this scope
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
^~~
game.cpp:58:10: note: suggested alternative: 'sz'
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
^~~
sz
game.cpp:68:10: error: 'tsz' was not declared in this scope
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
^~~
game.cpp:68:10: note: suggested alternative: 'sz'
tree[tsz].l=tree[p].l; tree[tsz].r=tree[p].r; tree[tsz].s=tree[p].s; tree[tsz].e=tree[p].e;
^~~
sz
