oj.uz

답안 #254137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254137 2020-07-29T11:57:36 Z Saboon Election (BOI18_election) C++14
100 / 100
 1646 ms 58636 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 20;

string s;

struct node{
	int T, LT, RT;
	int C, LC, RC;
	node(){
		T = LT = RT = C = LC = RC = 0;
	}
} seg[4*maxn];

node merge(node fi, node se){
	node ret;
	int tmp = min(fi.RC, se.LT);
	fi.RC -= tmp, se.LT -= tmp;
	tmp = min(fi.RC, se.T);
	fi.RC -= tmp, se.T -= tmp, se.RT += tmp;
	tmp = min(fi.C, se.LT);
	fi.C -= tmp, fi.LC += tmp, se.LT -= tmp;
	tmp = min(fi.C, se.T);
	fi.C -= tmp, fi.LC += tmp, se.T -= tmp, se.RT += tmp;
	
	tmp = min(fi.RT, se.LC);
	fi.RT -= tmp, se.LC -= tmp;
	tmp = min(fi.RT, se.C);
	fi.RT -= tmp, se.C -= tmp, se.RC += tmp;
	tmp = min(fi.T, se.LC);
	fi.T -= tmp, fi.LT += tmp, se.LC -= tmp;
	tmp = min(fi.T, se.C);
	fi.T -= tmp, fi.LT += tmp, se.C -= tmp, se.RC += tmp;

	tmp = min(fi.RT, se.LT);
	fi.RT -= tmp, se.LT -= tmp, ret.T += tmp;
	ret.T += fi.T + se.T;
	ret.LT = fi.LT + se.LT;
	ret.RT = fi.RT + se.RT;
	ret.C = fi.C + se.C;
	ret.LC = fi.LC + se.LC;
	ret.RC = fi.RC + se.RC;
	return ret;
}

node get(int id, int L, int R, int l, int r){
	if (l <= L and R <= r)
		return seg[id];
	int mid = (L + R) >> 1;
	if (r <= mid)
		return get(2*id+0, L, mid, l, r);
	if (mid <= l)
		return get(2*id+1, mid, R, l, r);
	return merge(get(2*id+0, L, mid, l, r), get(2*id+1, mid, R, l, r));
}

void build(int id, int L, int R){
	if (L + 1 == R){
		if (s[L] == 'C')
			seg[id].C = 1;
		else
			seg[id].T = 1;
		return;
	}
	int mid = (L + R) >> 1;
	build(2*id+0, L, mid);
	build(2*id+1, mid, R);
	seg[id] = merge(seg[2*id+0], seg[2*id+1]);
	
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n >> s;
	build(1, 0, n);
	int q;
	cin >> q;
	while (q --){
		int l, r;
		cin >> l >> r;
		l --;
		auto it = get(1, 0, n, l, r);
		cout << it.T + it.LT + it.RT << '\n';
	}
}

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47360 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47360 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47360 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47360 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 230 ms 48736 KB Output is correct
7 Correct 216 ms 48632 KB Output is correct
8 Correct 232 ms 48632 KB Output is correct
9 Correct 207 ms 48760 KB Output is correct
10 Correct 227 ms 48732 KB Output is correct
11 Correct 217 ms 48888 KB Output is correct
12 Correct 222 ms 48760 KB Output is correct
13 Correct 228 ms 48888 KB Output is correct
14 Correct 220 ms 48888 KB Output is correct
15 Correct 230 ms 48724 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47360 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 28 ms 47352 KB Output is correct
4 Correct 29 ms 47360 KB Output is correct
5 Correct 29 ms 47360 KB Output is correct
6 Correct 230 ms 48736 KB Output is correct
7 Correct 216 ms 48632 KB Output is correct
8 Correct 232 ms 48632 KB Output is correct
9 Correct 207 ms 48760 KB Output is correct
10 Correct 227 ms 48732 KB Output is correct
11 Correct 217 ms 48888 KB Output is correct
12 Correct 222 ms 48760 KB Output is correct
13 Correct 228 ms 48888 KB Output is correct
14 Correct 220 ms 48888 KB Output is correct
15 Correct 230 ms 48724 KB Output is correct
16 Correct 1637 ms 57780 KB Output is correct
17 Correct 1641 ms 57380 KB Output is correct
18 Correct 1633 ms 57480 KB Output is correct
19 Correct 1470 ms 57152 KB Output is correct
20 Correct 1633 ms 57168 KB Output is correct
21 Correct 1615 ms 58508 KB Output is correct
22 Correct 1646 ms 58432 KB Output is correct
23 Correct 1595 ms 58636 KB Output is correct
24 Correct 1617 ms 58356 KB Output is correct
25 Correct 1638 ms 57996 KB Output is correct