Submission #835387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
835387	2023-08-23T14:01:32 Z	MetalPower	Bliskost (COI23_bliskost)	C++14	28 / 100	9 ms	2816 KB

Main

#include <bits/stdc++.h>
using namespace std;

const int MX = 1e5 + 10;

int N, Q;
string s, t;

struct segtree{
	int st[MX << 1];

	void upd(int p, int v){
		for(p += MX, st[p] += v, p >>= 1; p > 0; p >>= 1) st[p] = st[p << 1] + st[p << 1|1];
	}

	int que(int l, int r){
		int res = 0;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res += st[l++];
			if(r & 1) res += st[--r];
		}
		return res;
	}
} S;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> Q >> s >> t;

	if(Q == 0){
		int pre = 0;
		for(int i = 0; i < N; i++){
			int x = ((int) t[i] - (int) s[i] + 26) % 26;
			pre = (x - pre + 26) % 26;
		}
		if(pre == 0) cout << "da\n";
		else cout << "ne\n";
	}else{
		for(int i = N - 1; i >= 0; i--){
			int x = ((int) t[i] - (int) s[i] + 26) % 26;
			if((N - 1 - i) & 1) S.upd(i, -x);
			else S.upd(i, x);
		}
		if(S.que(0, N - 1) % 26 == 0) cout << "da\n";
		else cout << "ne\n";
		for(int i = 0; i < Q; i++){
			int p; char c; cin >> p >> c;
			int dif = ((int) c - (int) s[i] + 26) % 26;
			if((N - p - 1) & 1) S.upd(p, -dif);
			else S.upd(p, dif);
			s[i] = c;
			if(S.que(0, N - 1) % 26 == 0) cout << "da\n";
			else cout << "ne\n";
		}
	}
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	9 ms	2800 KB	Output is correct
32	Correct	8 ms	2800 KB	Output is correct
33	Correct	8 ms	2800 KB	Output is correct
34	Correct	8 ms	2800 KB	Output is correct
35	Correct	8 ms	2800 KB	Output is correct
36	Correct	8 ms	2816 KB	Output is correct
37	Correct	8 ms	2800 KB	Output is correct
38	Correct	8 ms	2800 KB	Output is correct
39	Correct	8 ms	2800 KB	Output is correct
40	Correct	8 ms	2800 KB	Output is correct
41	Correct	8 ms	2748 KB	Output is correct
42	Correct	8 ms	2800 KB	Output is correct
43	Correct	8 ms	2800 KB	Output is correct
44	Correct	8 ms	2672 KB	Output is correct
45	Correct	8 ms	2800 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Runtime error	1 ms	468 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Runtime error	1 ms	468 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	300 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	212 KB	Output is correct
31	Correct	9 ms	2800 KB	Output is correct
32	Correct	8 ms	2800 KB	Output is correct
33	Correct	8 ms	2800 KB	Output is correct
34	Correct	8 ms	2800 KB	Output is correct
35	Correct	8 ms	2800 KB	Output is correct
36	Correct	8 ms	2816 KB	Output is correct
37	Correct	8 ms	2800 KB	Output is correct
38	Correct	8 ms	2800 KB	Output is correct
39	Correct	8 ms	2800 KB	Output is correct
40	Correct	8 ms	2800 KB	Output is correct
41	Correct	8 ms	2748 KB	Output is correct
42	Correct	8 ms	2800 KB	Output is correct
43	Correct	8 ms	2800 KB	Output is correct
44	Correct	8 ms	2672 KB	Output is correct
45	Correct	8 ms	2800 KB	Output is correct
46	Runtime error	1 ms	468 KB	Execution killed with signal 11
47	Halted	0 ms	0 KB	-

Submission #835387

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 13.0 / 13.0

Subtask #4 0 / 12.0

Subtask #5 0 / 17.0

Subtask #6 0 / 43.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
13.0 / 13.0

Subtask #4
0 / 12.0

Subtask #5
0 / 17.0

Subtask #6
0 / 43.0