oj.uz

Submission #363743

# Submission time Handle Problem Language Result Execution time Memory
363743 2021-02-07T07:33:45 Z sofapuden Game (IOI13_game) C++14
0 / 100
 2 ms 1152 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+5;

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;

	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 && r->c != 0){
				exc();
				c->chno(l->c,r->c,y);
			}
			else {
				c = l->c;
			}
		}
		else{
			if(r == NULL)exr();
			if(c == NULL)exc();
			r->ch(x,y,val);
			if(l != NULL && l->c != 0){
				exc();
				c->chno(l->c,r->c,y);
			}
			else {
				c = r->c;
			}
		}
	}	
};

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) {}
      |  ^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 2 ms 1132 KB Output isn't correct
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 384 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 2 ms 1152 KB Output isn't correct
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 Incorrect 2 ms 1132 KB Output isn't correct
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 Incorrect 2 ms 1132 KB Output isn't correct
3 Halted 0 ms 0 KB -