oj.uz

Submission #363698

# Submission time Handle Problem Language Result Execution time Memory
363698 2021-02-06T22:03:37 Z sofapuden Game (IOI13_game) C++14
63 / 100
 2953 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 ex(){
		int mid = (lb+rb)>>1;
		l = new seg1d;
		l->init(lb,mid);
		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;
		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;
		}
		if(l == NULL)ex();
		l->ch(x,va);
		r->ch(x,va);
		val = gcd2(l->val,r->val);
	}
	inline void chno(seg1d *a, seg1d *b, int x){
		if(rb < x || lb > x)return;
		if(l == NULL)ex();
		if(a == NULL){
			val = b->val;
			if(rb == lb)return;
			l->chno(a,b->l,x);
			r->chno(a,b->r,x);
			return;
		}
		if(b == NULL){
			val = a->val;
			if(rb == lb)return;
			l->chno(a->l,b,x);
			r->chno(a->r,b,x);
			return;
		}
		val = gcd2(a->val,b->val);
		if(rb == lb)return;
		l->chno(a->l,b->l,x);
		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 ex(){
		ll mid = (lb+rb)>>1;
		l = new seg2d;
		l->init(lb,mid);
		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;
		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;}
		if(l == NULL)ex();
		if(c == NULL)exc();
		l->ch(x,y,val);
		r->ch(x,y,val);
		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 1388 KB Output is correct
3 Correct 3 ms 1388 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 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 748 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 492 KB Output is correct
4 Correct 1203 ms 141804 KB Output is correct
5 Correct 938 ms 141932 KB Output is correct
6 Correct 1241 ms 139756 KB Output is correct
7 Correct 1269 ms 139884 KB Output is correct
8 Correct 832 ms 83052 KB Output is correct
9 Correct 1356 ms 140256 KB Output is correct
10 Correct 1242 ms 139756 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 4 ms 1388 KB Output is correct
3 Correct 5 ms 1388 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 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1645 ms 46828 KB Output is correct
13 Correct 1976 ms 24812 KB Output is correct
14 Correct 690 ms 2284 KB Output is correct
15 Correct 2285 ms 38568 KB Output is correct
16 Correct 2056 ms 67964 KB Output is correct
17 Correct 1936 ms 45768 KB Output is correct
18 Correct 2881 ms 68180 KB Output is correct
19 Correct 2646 ms 68284 KB Output is correct
20 Correct 2565 ms 67644 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 4 ms 1388 KB Output is correct
3 Correct 3 ms 1388 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 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 1388 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 1260 ms 141988 KB Output is correct
13 Correct 1025 ms 142188 KB Output is correct
14 Correct 1268 ms 140036 KB Output is correct
15 Correct 1245 ms 139756 KB Output is correct
16 Correct 879 ms 83052 KB Output is correct
17 Correct 1417 ms 140444 KB Output is correct
18 Correct 1216 ms 139628 KB Output is correct
19 Correct 1677 ms 47036 KB Output is correct
20 Correct 1997 ms 25056 KB Output is correct
21 Correct 701 ms 2668 KB Output is correct
22 Correct 2285 ms 38764 KB Output is correct
23 Correct 2077 ms 67964 KB Output is correct
24 Correct 1930 ms 46184 KB Output is correct
25 Correct 2953 ms 68556 KB Output is correct
26 Correct 2674 ms 68508 KB Output is correct
27 Correct 2612 ms 67916 KB Output is correct
28 Runtime error 450 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 1388 KB Output is correct
3 Correct 3 ms 1388 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 1388 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 4 ms 1396 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1209 ms 141568 KB Output is correct
13 Correct 954 ms 141732 KB Output is correct
14 Correct 1212 ms 139920 KB Output is correct
15 Correct 1277 ms 139488 KB Output is correct
16 Correct 829 ms 82668 KB Output is correct
17 Correct 1254 ms 139944 KB Output is correct
18 Correct 1269 ms 139236 KB Output is correct
19 Correct 1655 ms 46760 KB Output is correct
20 Correct 1944 ms 24632 KB Output is correct
21 Correct 692 ms 2172 KB Output is correct
22 Correct 2279 ms 38380 KB Output is correct
23 Correct 2058 ms 67568 KB Output is correct
24 Correct 1903 ms 45588 KB Output is correct
25 Correct 2904 ms 67892 KB Output is correct
26 Correct 2636 ms 68092 KB Output is correct
27 Correct 2607 ms 67436 KB Output is correct
28 Runtime error 458 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -