oj.uz

답안 #97117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97117 2019-02-14T02:02:31 Z E869120 게임 (IOI13_game) C++14
37 / 100
 13000 ms 7684 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

long long gcd2(long long X, long long Y) {
	long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Node {
	long long val; int l, r;
};

class RangedSegmentTree {
	public:
	vector<Node> I; int size_a, size_b, AX, AY, BX, BY;
	
	void init(int H, int W) {
		I.push_back(Node{0LL, -1, -1});
		size_a = 1; while(size_a < H) size_a *= 2;
		size_b = 1; while(size_b < W) size_b *= 2;
	}
	
	void update_(int cx, int cy, long long t, int ax, int ay, int bx, int by, int u) {
		//cout << "cx = " << cx << ", cy = " << cy << ", t = " << t << ", ax = " << ax << ", ay = " << ay << ", bx = " << bx << ", by = " << by << ", u = " << u << endl;
		if (by - ay == 1) {
			I[u].val = t;
			return;
		}
		if (bx - ax != 1) {
			if (cx < ((ax + bx) >> 1)) {
				if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, ay, (ax + bx) >> 1, by, I[u].l);
			}
			else {
				if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, (ax + bx) >> 1, ay, bx, by, I[u].r);
			}
		}
		else {
			if (cy < ((ay + by) >> 1)) {
				if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, ay, bx, (ay + by) >> 1, I[u].l);
			}
			else {
				if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, (ay + by) >> 1, bx, by, I[u].r);
			}
		}
		long long B1 = 0; if(I[u].l >= 0) B1 = I[I[u].l].val;
		long long B2 = 0; if(I[u].r >= 0) B2 = I[I[u].r].val;
		
		I[u].val = gcd2(B1, B2);
		return;
	}
	
	void update(int cx, int cy, long long t) {
		update_(cx, cy, t, 0, 0, size_a, size_b, 0);
	}
	
	long long query_(int lx, int ly, int rx, int ry, int u) {
		if (AX <= lx && rx <= BX && AY <= ly && ry <= BY) return I[u].val;
		if (rx <= AX || BX <= lx || ry <= AY || BY <= ly) return 0;
		
		if (rx - lx != 1) {
			long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, (lx + rx) >> 1, ry, I[u].l);
			long long P2 = 0; if (I[u].r >= 0) P2 = query_((lx + rx) >> 1, ly, rx, ry, I[u].r);
			return gcd2(P1, P2);
		}
		else {
			long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, rx, (ly + ry) >> 1, I[u].l);
			long long P2 = 0; if (I[u].r >= 0) P2 = query_(lx, (ly + ry) >> 1, rx, ry, I[u].r);
			return gcd2(P1, P2);
		}
	}
	
	long long query(int ax, int ay, int bx, int by) {
		AX = ax; AY = ay; BX = bx; BY = by;
		return query_(0, 0, size_a, size_b, 0);
	}
};

RangedSegmentTree Z;

void init(int R, int C) {
	Z.init(R, C);
}

void update(int P, int Q, long long K) {
    Z.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return Z.query(P, Q, U + 1, V + 1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1016 ms 7468 KB Output is correct
5 Correct 508 ms 7656 KB Output is correct
6 Correct 1018 ms 4904 KB Output is correct
7 Correct 1103 ms 3868 KB Output is correct
8 Correct 694 ms 4112 KB Output is correct
9 Correct 1069 ms 4148 KB Output is correct
10 Correct 1029 ms 3544 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Execution timed out 13086 ms 4884 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 1004 ms 7312 KB Output is correct
13 Correct 505 ms 7632 KB Output is correct
14 Correct 927 ms 4840 KB Output is correct
15 Correct 1112 ms 3724 KB Output is correct
16 Correct 679 ms 4080 KB Output is correct
17 Correct 997 ms 4112 KB Output is correct
18 Correct 986 ms 3660 KB Output is correct
19 Execution timed out 13056 ms 4800 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1044 ms 7400 KB Output is correct
13 Correct 507 ms 7684 KB Output is correct
14 Correct 898 ms 4716 KB Output is correct
15 Correct 976 ms 3812 KB Output is correct
16 Correct 696 ms 4356 KB Output is correct
17 Correct 1004 ms 4048 KB Output is correct
18 Correct 770 ms 3428 KB Output is correct
19 Execution timed out 13022 ms 4984 KB Time limit exceeded
20 Halted 0 ms 0 KB -