Submission #502580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502580	2022-01-06T09:48:41 Z	amunduzbaev	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	958 ms	6092 KB

monochrome

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

#define ar array

const int N = 4e5 + 5;

struct BIT{
	int tree[N];
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int rr = 0;
		for(;i>0;i-=(i&-i)) rr += tree[i];
		return rr;
	}
	
	int get(int l, int r){
		return get(r) - get(l-1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	ar<vector<int>, 2> p;
	for(int i=0;i<2*n;i++){
		p[s[i] == 'B'].push_back(i);
	}
	
	auto check = [&](int k){
		memset(tree.tree, 0, sizeof tree.tree);
		int res = 0;
		vector<ar<int, 2>> a(n);
		for(int i=0;i<n;i++){
			int j = (i + k) % n;
			a[i] = {p[0][i], p[1][j]};
			if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
		}
		
		sort(a.begin(), a.end());
		for(auto x : a){
			res += tree.get(x[0], x[1]);
			tree.add(x[1], 1);
		} return res;
	};
	
	int l = 0, r = n - 1;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m) < check(m + 1)) l = m + 1;
		else r = m;
	}
	
	cout<<check(l)<<"\n";
}

Subtask #1
4.0 / 4.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1868 KB	Output is correct
2	Correct	1 ms	1868 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	1 ms	1868 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	1 ms	1868 KB	Output is correct
7	Correct	1 ms	1868 KB	Output is correct
8	Correct	1 ms	1868 KB	Output is correct
9	Correct	1 ms	1868 KB	Output is correct
10	Correct	1 ms	1868 KB	Output is correct
11	Correct	1 ms	1868 KB	Output is correct
12	Correct	1 ms	1868 KB	Output is correct
13	Correct	1 ms	1868 KB	Output is correct
14	Correct	2 ms	1868 KB	Output is correct
15	Correct	3 ms	1888 KB	Output is correct
16	Correct	2 ms	1868 KB	Output is correct
17	Correct	2 ms	1868 KB	Output is correct
18	Correct	2 ms	1868 KB	Output is correct
19	Correct	2 ms	1868 KB	Output is correct
20	Correct	2 ms	1868 KB	Output is correct
21	Correct	2 ms	1788 KB	Output is correct
22	Correct	2 ms	1868 KB	Output is correct
23	Correct	2 ms	1868 KB	Output is correct
24	Correct	2 ms	1868 KB	Output is correct
25	Correct	2 ms	1868 KB	Output is correct
26	Correct	2 ms	1868 KB	Output is correct
27	Correct	2 ms	1868 KB	Output is correct
28	Correct	2 ms	1868 KB	Output is correct
29	Correct	2 ms	1868 KB	Output is correct
30	Correct	2 ms	1868 KB	Output is correct
31	Correct	2 ms	1888 KB	Output is correct
32	Correct	2 ms	1868 KB	Output is correct
33	Correct	2 ms	1868 KB	Output is correct
34	Correct	6 ms	1868 KB	Output is correct
35	Correct	6 ms	1852 KB	Output is correct
36	Correct	6 ms	1856 KB	Output is correct
37	Correct	6 ms	1932 KB	Output is correct
38	Correct	7 ms	1932 KB	Output is correct
39	Correct	6 ms	1928 KB	Output is correct
40	Correct	5 ms	1856 KB	Output is correct
41	Correct	7 ms	1940 KB	Output is correct
42	Correct	6 ms	1868 KB	Output is correct
43	Correct	6 ms	1840 KB	Output is correct
44	Correct	6 ms	1868 KB	Output is correct
45	Correct	6 ms	1848 KB	Output is correct
46	Correct	6 ms	1868 KB	Output is correct
47	Correct	5 ms	1860 KB	Output is correct
48	Correct	5 ms	1868 KB	Output is correct
49	Correct	5 ms	1868 KB	Output is correct
50	Correct	7 ms	1932 KB	Output is correct
51	Correct	6 ms	1860 KB	Output is correct
52	Correct	8 ms	1860 KB	Output is correct

Subtask #4
0.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1868 KB	Output is correct
2	Correct	1 ms	1868 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	1 ms	1868 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	1 ms	1868 KB	Output is correct
7	Correct	1 ms	1868 KB	Output is correct
8	Correct	1 ms	1868 KB	Output is correct
9	Correct	1 ms	1868 KB	Output is correct
10	Correct	1 ms	1868 KB	Output is correct
11	Correct	1 ms	1868 KB	Output is correct
12	Correct	1 ms	1868 KB	Output is correct
13	Correct	1 ms	1868 KB	Output is correct
14	Correct	2 ms	1868 KB	Output is correct
15	Correct	3 ms	1888 KB	Output is correct
16	Correct	2 ms	1868 KB	Output is correct
17	Correct	2 ms	1868 KB	Output is correct
18	Correct	2 ms	1868 KB	Output is correct
19	Correct	2 ms	1868 KB	Output is correct
20	Correct	2 ms	1868 KB	Output is correct
21	Correct	2 ms	1788 KB	Output is correct
22	Correct	2 ms	1868 KB	Output is correct
23	Correct	2 ms	1868 KB	Output is correct
24	Correct	2 ms	1868 KB	Output is correct
25	Correct	2 ms	1868 KB	Output is correct
26	Correct	2 ms	1868 KB	Output is correct
27	Correct	2 ms	1868 KB	Output is correct
28	Correct	2 ms	1868 KB	Output is correct
29	Correct	2 ms	1868 KB	Output is correct
30	Correct	2 ms	1868 KB	Output is correct
31	Correct	2 ms	1888 KB	Output is correct
32	Correct	2 ms	1868 KB	Output is correct
33	Correct	2 ms	1868 KB	Output is correct
34	Correct	6 ms	1868 KB	Output is correct
35	Correct	6 ms	1852 KB	Output is correct
36	Correct	6 ms	1856 KB	Output is correct
37	Correct	6 ms	1932 KB	Output is correct
38	Correct	7 ms	1932 KB	Output is correct
39	Correct	6 ms	1928 KB	Output is correct
40	Correct	5 ms	1856 KB	Output is correct
41	Correct	7 ms	1940 KB	Output is correct
42	Correct	6 ms	1868 KB	Output is correct
43	Correct	6 ms	1840 KB	Output is correct
44	Correct	6 ms	1868 KB	Output is correct
45	Correct	6 ms	1848 KB	Output is correct
46	Correct	6 ms	1868 KB	Output is correct
47	Correct	5 ms	1860 KB	Output is correct
48	Correct	5 ms	1868 KB	Output is correct
49	Correct	5 ms	1868 KB	Output is correct
50	Correct	7 ms	1932 KB	Output is correct
51	Correct	6 ms	1860 KB	Output is correct
52	Correct	8 ms	1860 KB	Output is correct
53	Incorrect	958 ms	6092 KB	Output isn't correct
54	Halted	0 ms	0 KB	-

Submission #502580

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 21.0 / 21.0

Subtask #3 10.0 / 10.0

Subtask #4 0.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
21.0 / 21.0

Subtask #3
10.0 / 10.0

Subtask #4
0.0 / 65.0