oj.uz

Submission #363708

# Submission time Handle Problem Language Result Execution time Memory
363708 2021-02-06T22:55:43 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2508 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+423764283;

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 3 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 1024 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 1004 KB Output is correct
10 Correct 1 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 885 ms 89004 KB Output is correct
5 Correct 660 ms 88756 KB Output is correct
6 Correct 919 ms 85928 KB Output is correct
7 Correct 999 ms 85612 KB Output is correct
8 Correct 606 ms 49900 KB Output is correct
9 Correct 970 ms 86020 KB Output is correct
10 Correct 923 ms 85484 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 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 1004 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1354 ms 30464 KB Output is correct
13 Correct 1808 ms 15708 KB Output is correct
14 Correct 417 ms 1516 KB Output is correct
15 Correct 2084 ms 24096 KB Output is correct
16 Correct 1693 ms 40940 KB Output is correct
17 Correct 1506 ms 27884 KB Output is correct
18 Correct 2507 ms 41452 KB Output is correct
19 Correct 2168 ms 41500 KB Output is correct
20 Correct 2174 ms 40948 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 3 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 492 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 1004 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 855 ms 88516 KB Output is correct
13 Correct 649 ms 88648 KB Output is correct
14 Correct 897 ms 86132 KB Output is correct
15 Correct 1022 ms 85740 KB Output is correct
16 Correct 595 ms 49956 KB Output is correct
17 Correct 1045 ms 86252 KB Output is correct
18 Correct 993 ms 85484 KB Output is correct
19 Correct 1339 ms 30308 KB Output is correct
20 Correct 1830 ms 15720 KB Output is correct
21 Correct 421 ms 1516 KB Output is correct
22 Correct 2029 ms 24048 KB Output is correct
23 Correct 1667 ms 41268 KB Output is correct
24 Correct 1505 ms 28016 KB Output is correct
25 Correct 2508 ms 41356 KB Output is correct
26 Correct 2208 ms 41520 KB Output is correct
27 Correct 2106 ms 40836 KB Output is correct
28 Runtime error 659 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 3 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 1004 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 836 ms 88620 KB Output is correct
13 Correct 633 ms 88680 KB Output is correct
14 Correct 904 ms 85904 KB Output is correct
15 Correct 977 ms 85868 KB Output is correct
16 Correct 672 ms 49900 KB Output is correct
17 Correct 982 ms 86120 KB Output is correct
18 Correct 940 ms 85516 KB Output is correct
19 Correct 1323 ms 30300 KB Output is correct
20 Correct 1881 ms 15748 KB Output is correct
21 Correct 427 ms 1516 KB Output is correct
22 Correct 2027 ms 24016 KB Output is correct
23 Correct 1692 ms 41104 KB Output is correct
24 Correct 1502 ms 27884 KB Output is correct
25 Correct 2468 ms 41400 KB Output is correct
26 Correct 2108 ms 41452 KB Output is correct
27 Correct 2130 ms 40876 KB Output is correct
28 Runtime error 620 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -