| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 363812 |
2021-02-07T10:23:05 Z |
sofapuden |
Game (IOI13_game) |
C++14 |
|
1 ms |
492 KB |
#include "game.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
long long mxN = 1<<30;
struct seg1d{
int lb, rb;
ll val;
seg1d *l, *r;
seg1d () : l(NULL), r(NULL), val(0) {}
inline void init(int lx, int rx){
lb = lx, rb = rx;
}
inline void exl(){
int mid = (lb+rb)>>1;
l = new seg1d;
l->init(lb,mid);
}
inline void exr(){
int mid = (lb+rb)>>1;
r = new seg1d;
r->init(mid+1,rb);
}
ll getGCD(int llb, int rrb){
if(llb > rb || rrb < lb)return 0;
if(llb <= lb && rrb >= rb)return val;
if(l == NULL && r == NULL)return 0;
if(l == NULL)return r->getGCD(llb,rrb);
if(r == NULL)return l->getGCD(llb,rrb);
return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
}
inline void ch(int x, ll va){
if(rb < x || lb > x)return;
if(rb == x && lb == x){
val = va;
return;
}
int mid = (lb+rb)>>1;
if(mid >= x){
if(l == NULL)exl();
l->ch(x,va);
if(r == NULL)val = l->val;
else val = gcd2(l->val,r->val);
}
else{
if(r == NULL)exr();
r->ch(x,va);
if(l == NULL)val = r->val;
else val = gcd2(l->val,r->val);
}
}
inline void chno(seg1d *a, seg1d *b, int x){
if(rb < x || lb > x)return;
int mid = (lb+rb)>>1;
if(mid >= x){
if(a == NULL){
val = b->val;
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a,b->l,x);
return;
}
if(b == NULL){
val = a->val;
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a->l,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a->l,b->l,x);
}
else{
if(a == NULL){
val = b->val;
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a,b->r,x);
return;
}
if(b == NULL){
val = a->val;
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a->r,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a->r,b->r,x);
}
}
};
struct seg2d{
int lb, rb;
seg2d *l, *r;
seg1d *c;
int pt;
seg2d () : l(NULL), r(NULL), c(NULL), pt(NULL) {}
inline void init(int lx, int rx){
lb = lx, rb = rx;
}
inline void exl(){
int mid = (lb+rb)>>1;
l = new seg2d;
l->init(lb,mid);
}
inline void exr(){
int mid = (lb+rb)>>1;
r = new seg2d;
r->init(mid+1,rb);
}
inline void exc(){
c = new seg1d;
c->init(0, mxN);
}
ll getGCD(int llb, int rrb, int uub, int ddb){
if(llb > rb || rrb < lb)return 0;
if(llb <= lb && rrb >= rb){
if(pt == NULL){ if(c == NULL)return 0;
return c->getGCD(uub,ddb);
}
if(pt == 1){
return l->getGCD(llb,rrb,uub,ddb);
}
if(pt == 2){
return r->getGCD(llb,rrb,uub,ddb);
}
}
if(l == NULL && r == NULL)return 0;
if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
}
inline void ch(int x, int y, ll val){
if(rb < x || lb > x)return;
if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
int mid = (rb+lb)>>1;
if(mid >= x){
if(l == NULL)exl();
if(c == NULL)exc();
l->ch(x,y,val);
if(r == NULL){
pt = 1;
}
else{
pt = NULL;
c->chno(l->c,r->c,y);
}
}
else{
if(r == NULL)exr();
if(c == NULL)exc();
r->ch(x,y,val);
if(l == NULL){
pt = 2;
}
else{
pt = NULL;
c->chno(l->c,r->c,y);
}
}
}
};
seg2d root;
void init(int R, int C) {
root.init(0,mxN);
}
void update(int P, int Q, long long K) {
root.ch(P+1,Q+1,K);
}
long long calculate(int P, int Q, int U, int V) {
return root.getGCD(P+1,U+1,Q+1,V+1);
}
Compilation message
game.cpp: In constructor 'seg1d::seg1d()':
game.cpp:25:13: warning: 'seg1d::r' will be initialized after [-Wreorder]
25 | seg1d *l, *r;
| ^
game.cpp:23:5: warning: 'll seg1d::val' [-Wreorder]
23 | ll val;
| ^~~
game.cpp:27:2: warning: when initialized here [-Wreorder]
27 | seg1d () : l(NULL), r(NULL), val(0) {}
| ^~~~~
game.cpp: In constructor 'seg2d::seg2d()':
game.cpp:128:43: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]
128 | seg2d () : l(NULL), r(NULL), c(NULL), pt(NULL) {}
| ^~~~
game.cpp: In member function 'll seg2d::getGCD(int, int, int, int)':
game.cpp:152:13: warning: NULL used in arithmetic [-Wpointer-arith]
152 | if(pt == NULL){ if(c == NULL)return 0;
| ^~~~
game.cpp: In member function 'void seg2d::ch(int, int, ll)':
game.cpp:180:10: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]
180 | pt = NULL;
| ^~~~
game.cpp:192:10: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]
192 | pt = NULL;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
