제출 #1173349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173349		altern23	Election (BOI18_election)	C++20	0 / 100	2 ms	576 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll MAXN = 3e5;
const ll INF = 4e18;
const ll MOD = 998244353;

struct ST{
	ll n;
	vector<ll> sg;
	ST(ll _n){
		n = _n;
		sg = vector<ll>(4 * n + 5);
	}
	
	void upd(ll l, ll r, ll cur, ll idx, ll val){
		if(l == r) sg[cur] = val;
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx, val);
			else upd(mid + 1, r, cur * 2 + 1, idx, val);
			sg[cur] = min(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	
	ll query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return INF;
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return min(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		string s; cin >> s;
		s = '%' + s;
		vector<ll> ps(N + 5), sf(N + 5);
		ST sp(N), ss(N);
		for(int i = 1; i <= N; i++){
			ps[i] = ps[i - 1] + (s[i] == 'C' ? 1 : -1);
			sp.upd(1, N, 1, i, ps[i]);
		}
		for(int i = N; i >= 1; --i){
			sf[i] = sf[i + 1] + (s[i] == 'C' ? 1 : -1);
			ss.upd(1, N, 1, i, sf[i]);
		}
		
		ll q; cin >> q;
		for(int i = 1; i <= q; i++){
			ll l, r; cin >> l >> r;
			ll A = max(0LL, -(sp.query(1, N, 1, l, r) - ps[l - 1]));
			ll B = max(0LL, -(ss.query(1, N, 1, l, r) - sf[r + 1]));
			cout << max(A, B) << "\n";
		}
	}   
}

/*

*/

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18