oj.uz

Submission #366365

# Submission time Handle Problem Language Result Execution time Memory
366365 2021-02-14T05:41:52 Z dennisstar Game (IOI13_game) C++17
80 / 100
 5124 ms 256004 KB 
#include <game.h>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int R, C;
struct dty {
	vector<int> L, R, K;
	vector<ll> st;
    dty() : L(2, 0), R(2, 0), K(2, -1), st(2, 0) {}
	int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		K.emplace_back(-1);
		st.emplace_back(0);
		return L.size()-1;
	}
	void upd(int i, int s, int e, int y, ll v) {
		if (s==e) { st[i]=v; return ; }
		int m=(s+e)/2;
		if (K.size()==2&&K[i]==-1) {
			K[i]=y;
			st[i]=v;
			return ;
		}
		if (K[i]!=-1) {
			if (K[i]==y) { st[i]=v; return ; }
			if (K[i]<=m) { L[i]=new_node(); K[L[i]]=K[i]; st[L[i]]=st[i]; }
			else { R[i]=new_node(); K[R[i]]=K[i]; st[R[i]]=st[i]; }
			K[i]=-1;
		}
		if (y<=m) {
			if (!L[i]) L[i]=new_node();
			upd(L[i], s, m, y, v);
		}
		else {
			if (!R[i]) R[i]=new_node();
			upd(R[i], m+1, e, y, v);
		}
		st[i]=__gcd(st[L[i]], st[R[i]]);
	}
	ll get(int i, int s, int e, int l, int r) {
		if (!i||e<l||r<s) return 0;
		if (K[i]!=-1) return (l<=K[i]&&K[i]<=r)?st[i]:0;
		int m=(s+e)/2;
		if (l<=s&&e<=r) return st[i];
		return __gcd(get(L[i], s, m, l, r), get(R[i], m+1, e, l, r));
	}
};

struct dtx {
    vector<dty> seg;
	vector<int> L, R;
    dtx() : L(2, 0), R(2, 0), seg(2, dty()) {}
	int new_node() {
		L.emplace_back(0);
		R.emplace_back(0);
		seg.emplace_back(dty());
		return L.size()-1;
	}
	void upd(int i, int s, int e, int x, int y, ll v) {
		if (s==e) {
			seg[i].upd(1, 0, C-1, y, v);
			return ;
		}
		int m=(s+e)/2;
		if (x<=m) {
			if (!L[i]) L[i]=new_node();
			upd(L[i], s, m, x, y, v);
		}
		else {
			if (!R[i]) R[i]=new_node();
			upd(R[i], m+1, e, x, y, v);
		}
		seg[i].upd(1, 0, C-1, y,
			__gcd(seg[L[i]].get(1, 0, C-1, y, y), seg[R[i]].get(1, 0, C-1, y, y)));
	}
	ll get(int i, int s, int e, int l, int r, int d, int u) {
		if (!i||e<l||r<s) return 0;
		if (l<=s&&e<=r) return seg[i].get(1, 0, C-1, d, u);
		int m=(s+e)/2;
		return __gcd(get(L[i], s, m, l, r, d, u), get(R[i], m+1, e, l, r, d, u));
	}
}S;

void init(int R, int C) {
	::R=R;
	::C=C;
}

void update(int P, int Q, ll K) {
	S.upd(1, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return S.get(1, 0, R-1, P, U, Q, V);
}

Compilation message

game.cpp: In constructor 'dtx::dtx()':
game.cpp:54:17: warning: 'dtx::R' will be initialized after [-Wreorder]
   54 |  vector<int> L, R;
      |                 ^
game.cpp:53:17: warning:   'std::vector<dty> dtx::seg' [-Wreorder]
   53 |     vector<dty> seg;
      |                 ^~~
game.cpp:55:5: warning:   when initialized here [-Wreorder]
   55 |     dtx() : L(2, 0), R(2, 0), seg(2, dty()) {}
      |     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 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 364 KB Output is correct
4 Correct 666 ms 15828 KB Output is correct
5 Correct 502 ms 15700 KB Output is correct
6 Correct 555 ms 12892 KB Output is correct
7 Correct 611 ms 12636 KB Output is correct
8 Correct 389 ms 10348 KB Output is correct
9 Correct 618 ms 12708 KB Output is correct
10 Correct 555 ms 12248 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 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1124 ms 19000 KB Output is correct
13 Correct 1623 ms 9708 KB Output is correct
14 Correct 336 ms 5868 KB Output is correct
15 Correct 1921 ms 12660 KB Output is correct
16 Correct 287 ms 20648 KB Output is correct
17 Correct 931 ms 15144 KB Output is correct
18 Correct 1702 ms 22300 KB Output is correct
19 Correct 1454 ms 22440 KB Output is correct
20 Correct 1374 ms 21800 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 658 ms 15956 KB Output is correct
13 Correct 506 ms 15816 KB Output is correct
14 Correct 546 ms 12968 KB Output is correct
15 Correct 619 ms 12592 KB Output is correct
16 Correct 387 ms 10344 KB Output is correct
17 Correct 595 ms 12632 KB Output is correct
18 Correct 556 ms 12248 KB Output is correct
19 Correct 1102 ms 19488 KB Output is correct
20 Correct 1625 ms 9760 KB Output is correct
21 Correct 340 ms 5756 KB Output is correct
22 Correct 1923 ms 12456 KB Output is correct
23 Correct 301 ms 20648 KB Output is correct
24 Correct 961 ms 15144 KB Output is correct
25 Correct 1712 ms 22244 KB Output is correct
26 Correct 1457 ms 22440 KB Output is correct
27 Correct 1374 ms 21800 KB Output is correct
28 Correct 1027 ms 117104 KB Output is correct
29 Correct 2274 ms 132796 KB Output is correct
30 Correct 5103 ms 114416 KB Output is correct
31 Correct 4904 ms 95996 KB Output is correct
32 Correct 781 ms 10520 KB Output is correct
33 Correct 959 ms 13624 KB Output is correct
34 Correct 677 ms 128164 KB Output is correct
35 Correct 1708 ms 69504 KB Output is correct
36 Correct 3355 ms 131020 KB Output is correct
37 Correct 2749 ms 131436 KB Output is correct
38 Correct 2667 ms 130392 KB Output is correct
39 Correct 2272 ms 113540 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 654 ms 15964 KB Output is correct
13 Correct 513 ms 15828 KB Output is correct
14 Correct 536 ms 12760 KB Output is correct
15 Correct 611 ms 12636 KB Output is correct
16 Correct 390 ms 10344 KB Output is correct
17 Correct 594 ms 12760 KB Output is correct
18 Correct 545 ms 12396 KB Output is correct
19 Correct 1094 ms 19052 KB Output is correct
20 Correct 1614 ms 9836 KB Output is correct
21 Correct 338 ms 5740 KB Output is correct
22 Correct 1915 ms 12584 KB Output is correct
23 Correct 288 ms 20776 KB Output is correct
24 Correct 955 ms 15332 KB Output is correct
25 Correct 1718 ms 22528 KB Output is correct
26 Correct 1438 ms 22312 KB Output is correct
27 Correct 1350 ms 21928 KB Output is correct
28 Correct 1028 ms 117064 KB Output is correct
29 Correct 2303 ms 132816 KB Output is correct
30 Correct 5124 ms 114636 KB Output is correct
31 Correct 4889 ms 96220 KB Output is correct
32 Correct 790 ms 10604 KB Output is correct
33 Correct 956 ms 13752 KB Output is correct
34 Correct 662 ms 128156 KB Output is correct
35 Correct 1685 ms 69808 KB Output is correct
36 Correct 3322 ms 131084 KB Output is correct
37 Correct 2746 ms 131176 KB Output is correct
38 Correct 2727 ms 130692 KB Output is correct
39 Correct 1595 ms 238684 KB Output is correct
40 Runtime error 3974 ms 256004 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -