oj.uz

Submission #363816

# Submission time Handle Problem Language Result Execution time Memory
363816 2021-02-07T10:27:29 Z sofapuden Game (IOI13_game) C++14
0 / 100
 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(0) {}
 
	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 == 0){ if(c == NULL)return 0;
				return c->getGCD(uub,ddb);
			}
			if(r == NULL){
				return l->getGCD(llb,rrb,uub,ddb);
			}
			if(l == NULL){
				return r->getGCD(llb,rrb,uub,ddb);
			}
			return 0;
		}
		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 = 0;
				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 = 0;
				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) {}
      |  ^~~~~

Subtask #1
0 / 10.0

# 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 -

Subtask #2
0 / 27.0

# 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 -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Runtime error 1 ms 492 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 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 -

Subtask #5
0 / 20.0

# 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 -