Submission #612604

#	Time	Username	Problem	Language	Result	Execution time	Memory
612604		amunduzbaev	Election (BOI18_election)	C++17	100 / 100	648 ms	47448 KiB

election

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;

const int N = 5e5 + 5;

struct ST{
	ar<int, 2> tree[N << 2];
	ar<int, 2> merge(ar<int, 2>& a, ar<int, 2>& b){
		ar<int, 2> c {};
		c[0] = a[0] + b[0];
		c[1] = max(b[1], b[0] + a[1]);
		return c;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x][0] = v, tree[x][1] = max(0, v);
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
	}
	ar<int, 2> ans;
	
	void get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			ans = merge(ans, tree[x]);
			return;
		} int m = (lx + rx) >> 1;
		get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1);
	}
}tree;

int l[N], r[N], res[N];
vector<int> Q[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	string s; cin >> s;
	int q; cin >> q;
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i]; r[i]--;
		Q[--l[i]].push_back(i);
	}
	
	deque<int> t;
	for(int i=n-1;~i;i--){
		if(s[i] == 'T'){
			t.push_front(i);
		} else {
			tree.set(i, -1);
			if(!t.empty()) tree.set(t.front(), 1), t.pop_front();
		}
		
		for(auto j : Q[i]){
			int c = upper_bound(t.begin(), t.end(), r[j]) - t.begin();
			tree.ans = {0, 0};
			tree.get(i, r[j]);
			res[j] = c + tree.ans[1];
		}
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

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