oj.uz

답안 #647026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647026 2022-10-01T12:16:29 Z 42kangaroo Election (BOI18_election) C++17
0 / 100
 2 ms 596 KB 
//
// Created by 42kangaroo on 01/10/2022.
//

#include "bits/stdc++.h"

using namespace std;

#define int long long

struct Val {
	int CSum, l, r, nul;

};

Val combine(const Val& l, const Val& r) {
	Val res{l.CSum + r.CSum, l.l + max((int)0,r.l - max((int)0, (l.CSum - l.nul))),r.r +max((int)0, l.r -  max((int)0,(r.CSum - r.nul))), 0};
	res.nul = max(res.l, res.r);
	return res;
}

pair<vector<bool>, int> input(){
	int n, q;
	cin  >> n;
	vector<bool> fans(n);
	for (auto&& f: fans) {
		char c;
		cin >> c;
		f = c == 'C';
	}
	cin >> q;
	return {fans, q};
}

struct SegTe {
	vector<Val> cache_;

	Val build(int l, int r, int i, const vector<bool>& inputVec) {
		if (l+1 >= r) return cache_[i] = (inputVec[l] ? Val{1, 0 ,0, 0} : Val{0, 1, 1, 1} );
		int m = (l + r) / 2;
		return cache_[i] = combine(build(l , m, 2*i+1, inputVec), build(m,r, 2*i+2, inputVec));
	}

	Val get(int l, int r, int i, int ql, int qr) {
		if (qr <= l || ql >= r) return {0,0,0, 0};
		if (ql <= l && qr >= r) return cache_[i];
		int m = (l+r)/2;
		return combine(get(l,m, 2*i+1, ql, qr), get(m,r,2*i+2, ql, qr));
	}

	SegTe(const vector<bool>& inputVec): cache_(inputVec.size()*4){
		build(0, inputVec.size(), 0, inputVec);
	}
};

signed main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
    auto [fans, q] = input();
	SegTe tree{fans};
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		cout << tree.get(0 ,fans.size(), 0 ,l-1, r).nul << "\n";
	}
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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