oj.uz

답안 #363696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363696 2021-02-06T22:00:02 Z sofapuden 게임 (IOI13_game) C++14
63 / 100
 2970 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));
	}

	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);
	}
	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));
	}

	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

# 결과 실행 시간 메모리 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 3 ms 748 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 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 1193 ms 141476 KB Output is correct
5 Correct 983 ms 141300 KB Output is correct
6 Correct 1175 ms 139500 KB Output is correct
7 Correct 1233 ms 139052 KB Output is correct
8 Correct 814 ms 82668 KB Output is correct
9 Correct 1282 ms 139884 KB Output is correct
10 Correct 1218 ms 139008 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 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 1630 ms 46488 KB Output is correct
13 Correct 1966 ms 24272 KB Output is correct
14 Correct 694 ms 1772 KB Output is correct
15 Correct 2298 ms 38076 KB Output is correct
16 Correct 2059 ms 67468 KB Output is correct
17 Correct 1874 ms 45392 KB Output is correct
18 Correct 2836 ms 67564 KB Output is correct
19 Correct 2570 ms 67664 KB Output is correct
20 Correct 2496 ms 66968 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 4 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 1277 ms 141292 KB Output is correct
13 Correct 956 ms 141552 KB Output is correct
14 Correct 1190 ms 139532 KB Output is correct
15 Correct 1228 ms 139276 KB Output is correct
16 Correct 823 ms 82540 KB Output is correct
17 Correct 1271 ms 139628 KB Output is correct
18 Correct 1197 ms 138988 KB Output is correct
19 Correct 1611 ms 46472 KB Output is correct
20 Correct 1941 ms 24308 KB Output is correct
21 Correct 710 ms 2008 KB Output is correct
22 Correct 2260 ms 37992 KB Output is correct
23 Correct 2025 ms 67412 KB Output is correct
24 Correct 1863 ms 45036 KB Output is correct
25 Correct 2956 ms 67576 KB Output is correct
26 Correct 2970 ms 67652 KB Output is correct
27 Correct 2713 ms 67224 KB Output is correct
28 Runtime error 473 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 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 1024 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 1606 ms 141932 KB Output is correct
13 Correct 963 ms 142060 KB Output is correct
14 Correct 1223 ms 139992 KB Output is correct
15 Correct 1254 ms 139728 KB Output is correct
16 Correct 868 ms 83088 KB Output is correct
17 Correct 1303 ms 140288 KB Output is correct
18 Correct 1226 ms 139500 KB Output is correct
19 Correct 1654 ms 47084 KB Output is correct
20 Correct 1956 ms 24940 KB Output is correct
21 Correct 702 ms 2540 KB Output is correct
22 Correct 2255 ms 38636 KB Output is correct
23 Correct 2028 ms 67776 KB Output is correct
24 Correct 1926 ms 45868 KB Output is correct
25 Correct 2901 ms 68172 KB Output is correct
26 Correct 2583 ms 68312 KB Output is correct
27 Correct 2541 ms 67564 KB Output is correct
28 Runtime error 463 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -