답안 #543307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543307	2022-03-30T06:11:10 Z	8e7	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	823 ms	7520 KB

monochrome

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], p[maxn];
int bp[maxn], wp[maxn];
struct BIT{
	int bit[maxn];
	void init(int n) {
		for (int i = 0;i <= n + 1;i++) bit[i] = 0;
	}
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;	
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
int main() {
	io
	int n;
	cin >> n;
	n *= 2;
	string s;
	cin >> s;
	int mi = 0, mpos = 0, cur = 0;
	for (int i = 0;i < n;i++) {
		if (cur < mi) {
			mi = cur;
			mpos = i;
		} 
		cur += (s[i] == 'B' ? 1 : -1);
	}
	int bi = 0, wi = 0;
	for (int i = 0;i < n;i++) {
		a[i] = (s[(mpos + i) % n] == 'B' ? 1 : -1);
		if (a[i] == 1) bp[bi++] = i;
		else wp[wi++] = i;
	}	
	auto getval = [&](int x) {
		for (int i = 0;i < n/2;i++) {
			p[bp[i]] = (i < x ? 1 : -1);
			p[wp[i]] = (i < n/2 - x ? 1 : -1);
		}
		int cur = 0;
		bit.init(n);
		ll ret = 0;
		int bi = 0, wi = 0;	
		//debug(x);
		//pary(p, p + n);
		for (int i = 0;i < n;i++) {
			cur += p[i];
			if (cur < 0) return 0LL;	
			if (p[i] == 1) {
				bit.modify(i, 1);
			} else {
				int cor = (a[i] > 0 ? wp[wi++] : bp[bi++]);
				//debug(i, cor);
				ret += bit.query(i) - bit.query(cor);	
				bit.modify(cor, -1);
			}
		}
		//debug(ret);
		return ret;
	};
	ll ans = 0;
	int lef = 0, rig = n / 2 + 1;
	while (lef < rig - 2) {
		int m1 = (2*lef + rig) / 3, m2 = (lef + 2 * rig) / 3;
		if (getval(m1) > getval(m2)) rig = m2;
		else lef = m1;
	}
	ans = max(ans, max(getval(lef), getval(lef + 1)));
	cout << ans << endl;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #2

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	328 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	328 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	328 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	328 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	328 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	328 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	7 ms	452 KB	Output is correct
35	Correct	6 ms	452 KB	Output is correct
36	Correct	6 ms	328 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	328 KB	Output is correct
41	Correct	7 ms	448 KB	Output is correct
42	Correct	6 ms	340 KB	Output is correct
43	Correct	6 ms	336 KB	Output is correct
44	Correct	6 ms	340 KB	Output is correct
45	Correct	6 ms	340 KB	Output is correct
46	Correct	5 ms	328 KB	Output is correct
47	Correct	6 ms	340 KB	Output is correct
48	Correct	6 ms	340 KB	Output is correct
49	Correct	5 ms	340 KB	Output is correct
50	Correct	6 ms	340 KB	Output is correct
51	Correct	6 ms	316 KB	Output is correct
52	Correct	5 ms	328 KB	Output is correct

Subtask #4

65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	328 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	328 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	328 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	7 ms	452 KB	Output is correct
35	Correct	6 ms	452 KB	Output is correct
36	Correct	6 ms	328 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	328 KB	Output is correct
41	Correct	7 ms	448 KB	Output is correct
42	Correct	6 ms	340 KB	Output is correct
43	Correct	6 ms	336 KB	Output is correct
44	Correct	6 ms	340 KB	Output is correct
45	Correct	6 ms	340 KB	Output is correct
46	Correct	5 ms	328 KB	Output is correct
47	Correct	6 ms	340 KB	Output is correct
48	Correct	6 ms	340 KB	Output is correct
49	Correct	5 ms	340 KB	Output is correct
50	Correct	6 ms	340 KB	Output is correct
51	Correct	6 ms	316 KB	Output is correct
52	Correct	5 ms	328 KB	Output is correct
53	Correct	823 ms	7400 KB	Output is correct
54	Correct	800 ms	7400 KB	Output is correct
55	Correct	799 ms	7172 KB	Output is correct
56	Correct	809 ms	7364 KB	Output is correct
57	Correct	758 ms	7392 KB	Output is correct
58	Correct	763 ms	7488 KB	Output is correct
59	Correct	754 ms	7144 KB	Output is correct
60	Correct	751 ms	7232 KB	Output is correct
61	Correct	780 ms	7328 KB	Output is correct
62	Correct	776 ms	7392 KB	Output is correct
63	Correct	750 ms	7272 KB	Output is correct
64	Correct	756 ms	7264 KB	Output is correct
65	Correct	722 ms	6920 KB	Output is correct
66	Correct	754 ms	7144 KB	Output is correct
67	Correct	732 ms	7168 KB	Output is correct
68	Correct	690 ms	6824 KB	Output is correct
69	Correct	756 ms	7520 KB	Output is correct
70	Correct	693 ms	6872 KB	Output is correct
71	Correct	754 ms	7520 KB	Output is correct
72	Correct	770 ms	7492 KB	Output is correct
73	Correct	763 ms	7508 KB	Output is correct