oj.uz

답안 #167486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167486 2019-12-08T16:43:54 Z cgiosy 게임 (IOI13_game) C++17
80 / 100
 6306 ms 256000 KB 
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;

struct T { ll x; int l, r; };
vector<T> X;
struct seg {
	int N, root;
	seg(const int n) : N(n-1) { root=-1; }
	ll get(int l, int r, int s, int e, int i) const {
		if(i==-1 || e<l || r<s) return 0;
		if(l<=s && e<=r) return X[i].x;
		int m=(s+e)>>1;
		return gcd(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
	}
	ll get(int l, int r) const { return get(l, r, 0, N, root); }
	ll set(int p, ll x, int s, int e, int&i) {
		if(p<s || e<p) return ~i ? X[i].x : 0;
		if(i==-1) {
			i=X.size();
			X.push_back({0, -1, -1});
		}
		if(s==e) return X[i].x=x;
		int m=(s+e)>>1;
		return X[i].x=gcd(set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r));
	}
	void set(int p, ll x) { set(p, x, 0, N, root); }
};

struct T2 { seg x; int l, r; };
vector<T2> Y;
struct seg2 {
	int N, M, root;
	seg2(int n, int m) : N(n-1), M(m) { root=-1; }
	ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
		if(i==-1 || e<l1 || r1<s) return 0;
		if(l1<=s && e<=r1) return Y[i].x.get(l2, r2);
		int m=(s+e)>>1;
		return gcd(get(l1, r1, l2, r2, s, m, Y[i].l), get(l1, r1, l2, r2, m+1, e, Y[i].r));
	}
	ll get(int l1, int r1, int l2, int r2) const { return get(l1, r1, l2, r2, 0, N, root); }
	ll set(int p, int q, ll x, int s, int e, int&i) {
		if(p<s || e<p) return ~i ? Y[i].x.get(q, q) : 0;
		if(i==-1) {
			i=Y.size();
			Y.push_back({seg(M), -1, -1});
		}
		if(s==e) {
			Y[i].x.set(q, x);
			return x;
		}
		int m=(s+e)>>1;
		ll y=gcd(set(p, q, x, s, m, Y[i].l), set(p, q, x, m+1, e, Y[i].r));
		Y[i].x.set(q, y);
		return y;
	}
	void set(int p, int q, ll x) { set(p, q, x, 0, N, root); }
} *T;

void init(int R, int C) {
	T=new seg2(R, C);
	X.reserve(1<<24);
	Y.reserve(1<<20);
}

void update(int P, int Q, ll K) {
	T->set(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return T->get(P, U, Q, V);
}

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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 791 ms 13036 KB Output is correct
5 Correct 605 ms 13100 KB Output is correct
6 Correct 674 ms 10460 KB Output is correct
7 Correct 746 ms 10148 KB Output is correct
8 Correct 483 ms 8824 KB Output is correct
9 Correct 726 ms 10308 KB Output is correct
10 Correct 656 ms 9976 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1393 ms 14456 KB Output is correct
13 Correct 2656 ms 7752 KB Output is correct
14 Correct 365 ms 5840 KB Output is correct
15 Correct 3150 ms 9504 KB Output is correct
16 Correct 272 ms 14028 KB Output is correct
17 Correct 1222 ms 11468 KB Output is correct
18 Correct 2249 ms 15404 KB Output is correct
19 Correct 1767 ms 15584 KB Output is correct
20 Correct 1701 ms 14948 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 799 ms 13012 KB Output is correct
13 Correct 578 ms 12920 KB Output is correct
14 Correct 694 ms 10564 KB Output is correct
15 Correct 770 ms 10188 KB Output is correct
16 Correct 493 ms 8604 KB Output is correct
17 Correct 750 ms 10316 KB Output is correct
18 Correct 670 ms 9912 KB Output is correct
19 Correct 1386 ms 14396 KB Output is correct
20 Correct 2573 ms 7716 KB Output is correct
21 Correct 365 ms 5988 KB Output is correct
22 Correct 3057 ms 9644 KB Output is correct
23 Correct 272 ms 13944 KB Output is correct
24 Correct 1186 ms 11632 KB Output is correct
25 Correct 2057 ms 15676 KB Output is correct
26 Correct 1824 ms 15548 KB Output is correct
27 Correct 1617 ms 15056 KB Output is correct
28 Correct 1037 ms 137076 KB Output is correct
29 Correct 2655 ms 151744 KB Output is correct
30 Correct 6306 ms 109392 KB Output is correct
31 Correct 5775 ms 85404 KB Output is correct
32 Correct 646 ms 10488 KB Output is correct
33 Correct 912 ms 11640 KB Output is correct
34 Correct 615 ms 145444 KB Output is correct
35 Correct 1776 ms 80712 KB Output is correct
36 Correct 3448 ms 149684 KB Output is correct
37 Correct 2714 ms 149768 KB Output is correct
38 Correct 2744 ms 149272 KB Output is correct
39 Correct 2344 ms 117336 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 779 ms 13184 KB Output is correct
13 Correct 585 ms 13048 KB Output is correct
14 Correct 717 ms 10488 KB Output is correct
15 Correct 751 ms 10088 KB Output is correct
16 Correct 518 ms 8676 KB Output is correct
17 Correct 767 ms 10488 KB Output is correct
18 Correct 668 ms 10012 KB Output is correct
19 Correct 1386 ms 14428 KB Output is correct
20 Correct 2567 ms 7780 KB Output is correct
21 Correct 365 ms 5724 KB Output is correct
22 Correct 3015 ms 9664 KB Output is correct
23 Correct 265 ms 13880 KB Output is correct
24 Correct 1194 ms 11768 KB Output is correct
25 Correct 2118 ms 15616 KB Output is correct
26 Correct 1795 ms 15580 KB Output is correct
27 Correct 1709 ms 15116 KB Output is correct
28 Correct 916 ms 136952 KB Output is correct
29 Correct 2348 ms 151628 KB Output is correct
30 Correct 6167 ms 109412 KB Output is correct
31 Correct 5761 ms 85300 KB Output is correct
32 Correct 661 ms 10360 KB Output is correct
33 Correct 919 ms 11512 KB Output is correct
34 Correct 599 ms 145404 KB Output is correct
35 Correct 1790 ms 80776 KB Output is correct
36 Correct 3188 ms 149620 KB Output is correct
37 Correct 2592 ms 149860 KB Output is correct
38 Correct 2680 ms 149196 KB Output is correct
39 Runtime error 1327 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -