oj.uz

답안 #364315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364315 2021-02-08T23:07:38 Z cheissmart Election (BOI18_election) C++14
0 / 100
 26 ms 31724 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 500005;

int n;
string s;

struct node {
	int ans, l, r, s;
	node(char c = 'C') {
		if(c == 'C') l = r = 0, ans = s = -1;
		else ans = l = r = s = 1;
	}
	node operator + (node t) {
		node res;
		res.s = s + t.s;
		res.l = max(l, s + t.l);
		res.r = max(r + t.s, t.r);
		res.ans = max({l + t.r, s + t.ans, t.s + ans});
		return res;
	}
} t[N * 4];

void build(int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(s[tl]);
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

node qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r) return t[v];
	int tm = (tl + tr) / 2;
	if(r <= tm) return qry(l, r, v * 2, tl, tm);
	else if(l >= tm) return qry(l, r, v * 2 + 1, tm, tr);
	else return qry(l, r, v * 2, tl, tm) + qry(l, r, v * 2 + 1, tm, tr);
}

signed main()
{
	IO_OP;

	cin >> n >> s;

	build();

	int q;
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		l--;
		cout << qry(l, r).ans << '\n';
	}

}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31724 KB Output isn't correct
2 Halted 0 ms 0 KB -