oj.uz

Submission #363704

# Submission time Handle Problem Language Result Execution time Memory
363704 2021-02-06T22:31:36 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2514 ms 256004 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;
				if(rb == lb)return;
				l->chno(a,b->l,x);
				return;
			}
			if(b == NULL){
				val = a->val;
				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) {}
      |  ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.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 Correct 1 ms 364 KB Output is correct
4 Correct 875 ms 87124 KB Output is correct
5 Correct 619 ms 87276 KB Output is correct
6 Correct 921 ms 84612 KB Output is correct
7 Correct 950 ms 84272 KB Output is correct
8 Correct 610 ms 49388 KB Output is correct
9 Correct 977 ms 84656 KB Output is correct
10 Correct 948 ms 84076 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 4 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1118 ms 30316 KB Output is correct
13 Correct 1490 ms 16236 KB Output is correct
14 Correct 432 ms 1772 KB Output is correct
15 Correct 1715 ms 24364 KB Output is correct
16 Correct 1294 ms 40836 KB Output is correct
17 Correct 1445 ms 27628 KB Output is correct
18 Correct 2492 ms 41172 KB Output is correct
19 Correct 2136 ms 41536 KB Output is correct
20 Correct 2065 ms 40872 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 3 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 901 ms 87096 KB Output is correct
13 Correct 615 ms 87148 KB Output is correct
14 Correct 922 ms 84844 KB Output is correct
15 Correct 984 ms 84356 KB Output is correct
16 Correct 614 ms 49260 KB Output is correct
17 Correct 996 ms 84712 KB Output is correct
18 Correct 942 ms 84108 KB Output is correct
19 Correct 1088 ms 30060 KB Output is correct
20 Correct 1467 ms 15852 KB Output is correct
21 Correct 424 ms 1388 KB Output is correct
22 Correct 1718 ms 23860 KB Output is correct
23 Correct 1316 ms 40560 KB Output is correct
24 Correct 1494 ms 27464 KB Output is correct
25 Correct 2514 ms 40896 KB Output is correct
26 Correct 2195 ms 41244 KB Output is correct
27 Correct 2123 ms 40212 KB Output is correct
28 Runtime error 640 ms 256004 KB Execution killed with signal 9
29 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 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 847 ms 86996 KB Output is correct
13 Correct 618 ms 86892 KB Output is correct
14 Correct 935 ms 84332 KB Output is correct
15 Correct 990 ms 84076 KB Output is correct
16 Correct 580 ms 49004 KB Output is correct
17 Correct 1022 ms 84540 KB Output is correct
18 Correct 911 ms 83820 KB Output is correct
19 Correct 1082 ms 30188 KB Output is correct
20 Correct 1442 ms 15596 KB Output is correct
21 Correct 403 ms 1516 KB Output is correct
22 Correct 1693 ms 23788 KB Output is correct
23 Correct 1333 ms 40684 KB Output is correct
24 Correct 1417 ms 27500 KB Output is correct
25 Correct 2457 ms 41016 KB Output is correct
26 Correct 2191 ms 40844 KB Output is correct
27 Correct 2032 ms 40428 KB Output is correct
28 Runtime error 619 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -