| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 363706 |
2021-02-06T22:45:32 Z |
sofapuden |
Game (IOI13_game) |
C++14 |
|
870 ms |
79212 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 = 1e9+69;
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(l == NULL)exl();
if(a == NULL){
val = b->val;
l = b->l;
//if(rb == lb)return;
//l->chno(a,b->l,x);
return;
}
if(b == NULL){
val = a->val;
l = a->l;
//if(rb == lb)return;
//l->chno(a->l,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
l->chno(a->l,b->l,x);
}
else{
if(r == NULL)exr();
if(a == NULL){
val = b->val;
if(rb == lb)return;
r->chno(a,b->r,x);
return;
}
if(b == NULL){
val = a->val;
if(rb == lb)return;
r->chno(a->r,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
r->chno(a->r,b->r,x);
}
}
};
struct seg2d{
int lb, rb;
seg2d *l, *r;
seg1d *c;
seg2d () : l(NULL), r(NULL), c(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(c == NULL)return 0;
return c->getGCD(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){
c->chno(l->c,l->c,y);
}
else{
c->chno(l->c,r->c,y);
}
}
else{
if(r == NULL)exr();
if(c == NULL)exc();
r->ch(x,y,val);
if(l == NULL){
c->chno(r->c,r->c,y);
}
else{
c->chno(l->c,r->c,y);
}
}
}
};
seg2d *root = new seg2d();
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) {}
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
876 KB |
Output isn't correct |
| 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 |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
870 ms |
79212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
