Submission #791428

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
791428	2023-07-24T06:21:03 Z	GEN 이지후(#10078)	Sličnost (COI23_slicnost)	C++17	24 / 100	3000 ms	524288 KB

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 530000;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> a1(n), a2(n);
	vector<int> r1(n), r2(n);
	for (int i = 0; i < n; i++) {
		cin >> a1[i];
		a1[i]--;
		r1[a1[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> a2[i];
		a2[i]--;
		r2[a2[i]] = i;
	}
	auto naive = [&]() {
		vector<vector<int>> dx(n + 1, vector<int>(n + 1));
		for (int i = 0; i < n; i++) {
			int x1 = max(k - 1, r1[i]), x2 = min(r1[i] + k, n);
			int y1 = max(k - 1, r2[i]), y2 = min(r2[i] + k, n);
			dx[x1][y1]++;
			dx[x1][y2]--;
			dx[x2][y1]--;
			dx[x2][y2]++;
		}
		lint mx = 0, mxc = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j)
					dx[i][j] += dx[i][j - 1];
				if (i)
					dx[i][j] += dx[i - 1][j];
				if (i && j)
					dx[i][j] -= dx[i - 1][j - 1];
				if (mx < dx[i][j]) {
					mx = dx[i][j];
					mxc = 0;
				}
				if (mx == dx[i][j]) {
					mxc++;
				}
			}
		}
		if (mx == 0)
			mxc = 1ll * (n - k + 1) * (n - k + 1);
		cout << mx << " " << mxc << "\n";
	};
	naive();
	while (q--) {
		int t;
		cin >> t;
		t--;
		int p1 = a1[t], p2 = a1[t + 1];
		swap(a1[t], a1[t + 1]);
		r1[p1]++;
		r1[p2]--;
		naive();
	}
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	162 ms	94156 KB	Output is correct
17	Correct	159 ms	92888 KB	Output is correct
18	Correct	157 ms	93084 KB	Output is correct
19	Correct	163 ms	94160 KB	Output is correct
20	Correct	165 ms	98180 KB	Output is correct
21	Correct	152 ms	90868 KB	Output is correct
22	Correct	163 ms	97428 KB	Output is correct
23	Correct	151 ms	89640 KB	Output is correct
24	Correct	159 ms	94608 KB	Output is correct
25	Correct	151 ms	89004 KB	Output is correct
26	Correct	165 ms	96204 KB	Output is correct
27	Correct	154 ms	90648 KB	Output is correct
28	Correct	153 ms	90328 KB	Output is correct
29	Correct	163 ms	96232 KB	Output is correct
30	Correct	158 ms	93784 KB	Output is correct

Subtask #3
0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	162 ms	94156 KB	Output is correct
17	Correct	159 ms	92888 KB	Output is correct
18	Correct	157 ms	93084 KB	Output is correct
19	Correct	163 ms	94160 KB	Output is correct
20	Correct	165 ms	98180 KB	Output is correct
21	Correct	152 ms	90868 KB	Output is correct
22	Correct	163 ms	97428 KB	Output is correct
23	Correct	151 ms	89640 KB	Output is correct
24	Correct	159 ms	94608 KB	Output is correct
25	Correct	151 ms	89004 KB	Output is correct
26	Correct	165 ms	96204 KB	Output is correct
27	Correct	154 ms	90648 KB	Output is correct
28	Correct	153 ms	90328 KB	Output is correct
29	Correct	163 ms	96232 KB	Output is correct
30	Correct	158 ms	93784 KB	Output is correct
31	Runtime error	267 ms	524288 KB	Execution killed with signal 9
32	Halted	0 ms	0 KB	-

Subtask #4
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	5 ms	340 KB	Output is correct
17	Correct	5 ms	356 KB	Output is correct
18	Correct	5 ms	340 KB	Output is correct
19	Correct	6 ms	340 KB	Output is correct
20	Correct	6 ms	340 KB	Output is correct
21	Correct	5 ms	340 KB	Output is correct
22	Correct	6 ms	340 KB	Output is correct
23	Correct	5 ms	340 KB	Output is correct
24	Correct	6 ms	340 KB	Output is correct
25	Correct	6 ms	340 KB	Output is correct
26	Correct	6 ms	340 KB	Output is correct
27	Correct	6 ms	360 KB	Output is correct
28	Correct	5 ms	340 KB	Output is correct
29	Correct	6 ms	360 KB	Output is correct
30	Correct	6 ms	340 KB	Output is correct

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	162 ms	94156 KB	Output is correct
17	Correct	159 ms	92888 KB	Output is correct
18	Correct	157 ms	93084 KB	Output is correct
19	Correct	163 ms	94160 KB	Output is correct
20	Correct	165 ms	98180 KB	Output is correct
21	Correct	152 ms	90868 KB	Output is correct
22	Correct	163 ms	97428 KB	Output is correct
23	Correct	151 ms	89640 KB	Output is correct
24	Correct	159 ms	94608 KB	Output is correct
25	Correct	151 ms	89004 KB	Output is correct
26	Correct	165 ms	96204 KB	Output is correct
27	Correct	154 ms	90648 KB	Output is correct
28	Correct	153 ms	90328 KB	Output is correct
29	Correct	163 ms	96232 KB	Output is correct
30	Correct	158 ms	93784 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	5 ms	356 KB	Output is correct
33	Correct	5 ms	340 KB	Output is correct
34	Correct	6 ms	340 KB	Output is correct
35	Correct	6 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct
37	Correct	6 ms	340 KB	Output is correct
38	Correct	5 ms	340 KB	Output is correct
39	Correct	6 ms	340 KB	Output is correct
40	Correct	6 ms	340 KB	Output is correct
41	Correct	6 ms	340 KB	Output is correct
42	Correct	6 ms	360 KB	Output is correct
43	Correct	5 ms	340 KB	Output is correct
44	Correct	6 ms	360 KB	Output is correct
45	Correct	6 ms	340 KB	Output is correct
46	Execution timed out	3039 ms	94344 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

Subtask #6
0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	162 ms	94156 KB	Output is correct
17	Correct	159 ms	92888 KB	Output is correct
18	Correct	157 ms	93084 KB	Output is correct
19	Correct	163 ms	94160 KB	Output is correct
20	Correct	165 ms	98180 KB	Output is correct
21	Correct	152 ms	90868 KB	Output is correct
22	Correct	163 ms	97428 KB	Output is correct
23	Correct	151 ms	89640 KB	Output is correct
24	Correct	159 ms	94608 KB	Output is correct
25	Correct	151 ms	89004 KB	Output is correct
26	Correct	165 ms	96204 KB	Output is correct
27	Correct	154 ms	90648 KB	Output is correct
28	Correct	153 ms	90328 KB	Output is correct
29	Correct	163 ms	96232 KB	Output is correct
30	Correct	158 ms	93784 KB	Output is correct
31	Runtime error	267 ms	524288 KB	Execution killed with signal 9
32	Halted	0 ms	0 KB	-

Submission #791428

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 33.0

Subtask #4 7.0 / 7.0

Subtask #5 0 / 10.0

Subtask #6 0 / 33.0

Subtask #1
7.0 / 7.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 33.0

Subtask #4
7.0 / 7.0

Subtask #5
0 / 10.0

Subtask #6
0 / 33.0