oj.uz

Submission #363750

# Submission time Handle Problem Language Result Execution time Memory
363750 2021-02-07T07:47:06 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2486 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+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){
				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;
 
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 876 KB Output is correct
3 Correct 2 ms 876 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 876 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 636 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 843 ms 74604 KB Output is correct
5 Correct 669 ms 74620 KB Output is correct
6 Correct 864 ms 72052 KB Output is correct
7 Correct 920 ms 71788 KB Output is correct
8 Correct 634 ms 43756 KB Output is correct
9 Correct 986 ms 72300 KB Output is correct
10 Correct 938 ms 71660 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 876 KB Output is correct
3 Correct 2 ms 876 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 876 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 492 KB Output is correct
12 Correct 1178 ms 26984 KB Output is correct
13 Correct 1470 ms 14464 KB Output is correct
14 Correct 421 ms 2540 KB Output is correct
15 Correct 1742 ms 20972 KB Output is correct
16 Correct 1343 ms 36076 KB Output is correct
17 Correct 1463 ms 24936 KB Output is correct
18 Correct 2486 ms 36076 KB Output is correct
19 Correct 2074 ms 36204 KB Output is correct
20 Correct 2049 ms 35932 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 876 KB Output is correct
3 Correct 2 ms 876 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 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 883 ms 74696 KB Output is correct
13 Correct 595 ms 74860 KB Output is correct
14 Correct 875 ms 72172 KB Output is correct
15 Correct 929 ms 72044 KB Output is correct
16 Correct 594 ms 43704 KB Output is correct
17 Correct 897 ms 72300 KB Output is correct
18 Correct 877 ms 71456 KB Output is correct
19 Correct 1120 ms 26964 KB Output is correct
20 Correct 1435 ms 14228 KB Output is correct
21 Correct 400 ms 2412 KB Output is correct
22 Correct 1657 ms 20984 KB Output is correct
23 Correct 1276 ms 35708 KB Output is correct
24 Correct 1355 ms 24812 KB Output is correct
25 Correct 2285 ms 36076 KB Output is correct
26 Correct 1997 ms 36204 KB Output is correct
27 Correct 1939 ms 35436 KB Output is correct
28 Runtime error 651 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 896 KB Output is correct
3 Correct 2 ms 888 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 876 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 492 KB Output is correct
12 Correct 831 ms 75116 KB Output is correct
13 Correct 598 ms 75244 KB Output is correct
14 Correct 871 ms 72556 KB Output is correct
15 Correct 957 ms 72428 KB Output is correct
16 Correct 587 ms 44268 KB Output is correct
17 Correct 919 ms 72812 KB Output is correct
18 Correct 882 ms 72172 KB Output is correct
19 Correct 1071 ms 27628 KB Output is correct
20 Correct 1447 ms 14964 KB Output is correct
21 Correct 399 ms 3180 KB Output is correct
22 Correct 1674 ms 21560 KB Output is correct
23 Correct 1281 ms 36404 KB Output is correct
24 Correct 1441 ms 25472 KB Output is correct
25 Correct 2393 ms 36716 KB Output is correct
26 Correct 2044 ms 37152 KB Output is correct
27 Correct 1994 ms 36260 KB Output is correct
28 Runtime error 652 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -