oj.uz

답안 #281529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281529 2020-08-23T05:47:28 Z Atalasion Election (BOI18_election) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

struct node{
	int mn, mx, Rmx, Lmn;
};

node seg[N << 2];
int n, q, ps[N], ted[N];
string s;

node merge(node x, node y){
	node res = x;
	res.mx = y.mx, res.Rmx = y.Rmx;
	if (res.mn > y.mn) res.mn = y.mn, res.Lmn = y.Lmn;
	if (x.mx > res.mx) res.mx = x.mx, res.Rmx = x.Rmx;
	return res;
}

void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].mn = seg[id].mx = ps[l], seg[id].Rmx = seg[id].Lmn = l;
		return;
	}
	int md = (l + r) >> 1;
	build(id << 1, l, md);
	build(id << 1 | 1, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

node get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq){
		node res;
		res.mx = -INF, res.mn = INF;
		return res;
	}
	if (lq <= l && r <= rq) return seg[id];
	int md = (l + r) >> 1;
	return merge(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}

int SZ(int L, int R, int LL, int RR){
	int l = max(L, LL), r = min(R, RR);
	if(r < l) return 0;
	return ted[r] - ted[l - 1];
}

pii baze(int L, int R, int LL, int RR){
	int l = max(L, LL), r = min(R, RR);
	return {l,r};
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++){
		ted[i] = ted[i - 1];
		if (s[i - 1] == 'C') ps[i] = ps[i - 1] + 1;
		else ps[i] = ps[i - 1] - 1, ted[i]++;
	}
	build(1, 0, n + 1);
	cin >> q;
	for (int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		node res = get(1, l - 1, r + 1, 0, n + 1);
		int L, R;
		int ans = 0;
		if (res.mx <= ps[r]) L = n + 1, R = n + 1;
		else L = res.Rmx + 1, R = r;
		int LL, RR;
		if (res.mn >= ps[l - 1]) LL = 0, RR = 0;
		else LL = l, RR = res.Lmn;
		int x = SZ(L, R, LL, RR);
		int val1 = res.mx - ps[r], val2 = ps[l - 1] - res.mn;
		if (x == 0){
			ans += val1 + val2;
			cout << ans << '\n';
			continue;
		}
		pii Now = baze(L, R, LL, RR);
		res = get(1, Now.S, r + 1, 0, n + 1);
		val1 -= max(0, res.mx - ps[r]);
		ans += (0, res.mx - ps[r]);
		res = get(1, l - 1, Now.F, 0, n + 1);
		val2 -= max(0, ps[l - 1] - res.mn);
		ans += (0, ps[l - 1] - res.mn);
		ans += min({val1, val2, x});
		ans += (val1 - ans) + (val2 - ans);
		cout << ans << '\n';
	}
	return 0;
}

Compilation message

election.cpp: In function 'int32_t main()':
election.cpp:101:11: warning: left operand of comma operator has no effect [-Wunused-value]
  101 |   ans += (0, res.mx - ps[r]);
      |           ^
election.cpp:104:11: warning: left operand of comma operator has no effect [-Wunused-value]
  104 |   ans += (0, ps[l - 1] - res.mn);
      |           ^

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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