oj.uz

Submission #363713

# Submission time Handle Problem Language Result Execution time Memory
363713 2021-02-06T23:30:59 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2382 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 = 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 876 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 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 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 376 KB Output is correct
4 Correct 847 ms 73404 KB Output is correct
5 Correct 588 ms 73468 KB Output is correct
6 Correct 869 ms 70924 KB Output is correct
7 Correct 937 ms 70572 KB Output is correct
8 Correct 572 ms 42348 KB Output is correct
9 Correct 905 ms 71020 KB Output is correct
10 Correct 889 ms 70508 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 1074 ms 25848 KB Output is correct
13 Correct 1440 ms 13244 KB Output is correct
14 Correct 403 ms 1476 KB Output is correct
15 Correct 1680 ms 20216 KB Output is correct
16 Correct 1268 ms 34924 KB Output is correct
17 Correct 1413 ms 23916 KB Output is correct
18 Correct 2374 ms 35208 KB Output is correct
19 Correct 2063 ms 35032 KB Output is correct
20 Correct 1959 ms 34420 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 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 823 ms 73452 KB Output is correct
13 Correct 596 ms 73580 KB Output is correct
14 Correct 856 ms 71020 KB Output is correct
15 Correct 947 ms 70720 KB Output is correct
16 Correct 582 ms 42476 KB Output is correct
17 Correct 917 ms 71020 KB Output is correct
18 Correct 894 ms 70380 KB Output is correct
19 Correct 1074 ms 25836 KB Output is correct
20 Correct 1433 ms 13164 KB Output is correct
21 Correct 404 ms 1516 KB Output is correct
22 Correct 1678 ms 20176 KB Output is correct
23 Correct 1271 ms 34796 KB Output is correct
24 Correct 1392 ms 23660 KB Output is correct
25 Correct 2354 ms 35180 KB Output is correct
26 Correct 2051 ms 35448 KB Output is correct
27 Correct 1959 ms 34572 KB Output is correct
28 Runtime error 643 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 492 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 572 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 824 ms 73324 KB Output is correct
13 Correct 586 ms 73472 KB Output is correct
14 Correct 857 ms 70764 KB Output is correct
15 Correct 928 ms 70892 KB Output is correct
16 Correct 576 ms 42476 KB Output is correct
17 Correct 917 ms 71276 KB Output is correct
18 Correct 938 ms 70472 KB Output is correct
19 Correct 1073 ms 25964 KB Output is correct
20 Correct 1428 ms 13164 KB Output is correct
21 Correct 400 ms 1352 KB Output is correct
22 Correct 1680 ms 20304 KB Output is correct
23 Correct 1271 ms 34796 KB Output is correct
24 Correct 1417 ms 23660 KB Output is correct
25 Correct 2382 ms 35156 KB Output is correct
26 Correct 2084 ms 35308 KB Output is correct
27 Correct 1988 ms 34540 KB Output is correct
28 Runtime error 645 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -