Submission #1050465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050465		vako_p	Election (BOI18_election)	C++14	100 / 100	483 ms	44744 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 5e5 + 5;
ll n,qq,ans[mxN];
pair<ll,pair<ll,ll>> q[mxN];
char ch[mxN];

struct segtree{
	vector<ll> v,v1;
	ll sz = 1;
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, 0LL);
		v1.assign(2 * sz, 0LL);
	}
	
	void set(ll val, ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return;
		if(lx >= l and rx <= r){
			v1[x] += val;
			v[x] += val;
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		set(val, l, r, 2 * x + 1, lx, mid);
		set(val, l, r, 2 * x + 2, mid, rx);
		v[x] = min(v[2 * x + 1], v[2 * x + 2]) + v1[x]; 
	}
	
	void set(ll val, ll l, ll r){
		set(val, l, r, 0, 0, sz);
	}
	
	ll find(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return 1e16;
		if(lx >= l and rx <= r) return v[x];
		ll mid = lx + (rx - lx) / 2;
		return (min(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx)) + v1[x]);
	}
	
	ll find(ll l, ll r){
		return find(l, r, 0, 0, sz);	
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	segtree s;
	s.init();
	for(int i = 0; i < n; i++){
		cin >> ch[i];
	}
	cin >> qq;
	for(int i = 0; i < qq; i++){
		cin >> q[i].second.first >> q[i].first;
		q[i].first--;
		q[i].second.first--;
		q[i].second.second = i; 
	}
	sort(q, q + qq);
	vector<ll> st;
	ll l1 = 0;
	for(int i = 0; i < qq; i++){
		ll l = q[i].second.first, r = q[i].first;
//		cout << l << ' ' << r << '\n';
		while(l1 <= r){
			if(ch[l1] == 'T') st.pb(l1);
			else{
				s.set(1, l1, n);
				if(!st.empty()){
					s.set(-1, st[st.size() - 1], n);
					st.pop_back(); 
				}
			}
			l1++;
//			cout << l1 << '\n';
		}
		ll x,sz = st.size();
		auto it = lower_bound(st.begin(), st.end(), l);
		if(it == st.end()) x = 0;
	 	else x = sz - (it - st.begin());
//		cout << s.find(l - 1, l) << '\n';
		if(l) ans[q[i].second.second] = max(0LL, -(s.find(l, r) - s.find(l - 1, l))) + x;
		else ans[q[i].second.second] = max(0LL, -(s.find(l, r))) + x;
	}
	for(int i = 0; i < qq; i++) cout << ans[i] << '\n';
}

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