oj.uz

Submission #167488

# Submission time Handle Problem Language Result Execution time Memory
167488 2019-12-08T16:56:26 Z cgiosy Game (IOI13_game) C++17
80 / 100
 6384 ms 256004 KB 
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;
int sz1=0, sz2=0;

struct T { ll x; int l, r; } X[1<<26];
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) X[i=sz1++]={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; } Y[1<<22];
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) Y[i=sz2++]={new 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);
}
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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 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 0 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 815 ms 10716 KB Output is correct
5 Correct 589 ms 11000 KB Output is correct
6 Correct 707 ms 8056 KB Output is correct
7 Correct 762 ms 8148 KB Output is correct
8 Correct 502 ms 6712 KB Output is correct
9 Correct 753 ms 8440 KB Output is correct
10 Correct 689 ms 7912 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory 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 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1355 ms 12684 KB Output is correct
13 Correct 2589 ms 6380 KB Output is correct
14 Correct 371 ms 4032 KB Output is correct
15 Correct 3047 ms 8104 KB Output is correct
16 Correct 277 ms 12436 KB Output is correct
17 Correct 1271 ms 10140 KB Output is correct
18 Correct 2124 ms 14052 KB Output is correct
19 Correct 1731 ms 14496 KB Output is correct
20 Correct 1625 ms 13780 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory 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 2 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 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 812 ms 11716 KB Output is correct
13 Correct 595 ms 11548 KB Output is correct
14 Correct 700 ms 9184 KB Output is correct
15 Correct 811 ms 8924 KB Output is correct
16 Correct 525 ms 7544 KB Output is correct
17 Correct 758 ms 9112 KB Output is correct
18 Correct 677 ms 8604 KB Output is correct
19 Correct 1382 ms 13344 KB Output is correct
20 Correct 2593 ms 6780 KB Output is correct
21 Correct 374 ms 4648 KB Output is correct
22 Correct 3040 ms 8588 KB Output is correct
23 Correct 271 ms 13048 KB Output is correct
24 Correct 1256 ms 10688 KB Output is correct
25 Correct 2124 ms 14228 KB Output is correct
26 Correct 1807 ms 14496 KB Output is correct
27 Correct 1655 ms 13992 KB Output is correct
28 Correct 974 ms 136232 KB Output is correct
29 Correct 2446 ms 151448 KB Output is correct
30 Correct 6348 ms 110476 KB Output is correct
31 Correct 5853 ms 86060 KB Output is correct
32 Correct 722 ms 6260 KB Output is correct
33 Correct 969 ms 7520 KB Output is correct
34 Correct 597 ms 149268 KB Output is correct
35 Correct 1913 ms 78288 KB Output is correct
36 Correct 3550 ms 148904 KB Output is correct
37 Correct 2901 ms 149104 KB Output is correct
38 Correct 2911 ms 148368 KB Output is correct
39 Correct 2284 ms 115808 KB Output is correct
40 Correct 2 ms 376 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 380 KB Output is correct
5 Correct 2 ms 256 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 2 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 793 ms 12568 KB Output is correct
13 Correct 650 ms 12420 KB Output is correct
14 Correct 730 ms 9984 KB Output is correct
15 Correct 766 ms 9760 KB Output is correct
16 Correct 500 ms 8292 KB Output is correct
17 Correct 741 ms 9960 KB Output is correct
18 Correct 673 ms 9748 KB Output is correct
19 Correct 1447 ms 14156 KB Output is correct
20 Correct 2668 ms 7484 KB Output is correct
21 Correct 387 ms 5428 KB Output is correct
22 Correct 3044 ms 9348 KB Output is correct
23 Correct 266 ms 13848 KB Output is correct
24 Correct 1273 ms 11688 KB Output is correct
25 Correct 2153 ms 15612 KB Output is correct
26 Correct 1847 ms 15872 KB Output is correct
27 Correct 1708 ms 15256 KB Output is correct
28 Correct 966 ms 136148 KB Output is correct
29 Correct 2376 ms 151996 KB Output is correct
30 Correct 6384 ms 110428 KB Output is correct
31 Correct 5843 ms 85780 KB Output is correct
32 Correct 702 ms 5720 KB Output is correct
33 Correct 965 ms 7064 KB Output is correct
34 Correct 660 ms 148976 KB Output is correct
35 Correct 1921 ms 78148 KB Output is correct
36 Correct 3466 ms 148860 KB Output is correct
37 Correct 2789 ms 148656 KB Output is correct
38 Correct 2758 ms 148408 KB Output is correct
39 Runtime error 1238 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -