Submission #321273

#	Time	Username	Problem	Language	Result	Execution time	Memory
321273		kapsel	Election (BOI18_election)	C++17	100 / 100	584 ms	53104 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

typedef pair<int, int> pi;

const int INF = 1e9 + 2137;

struct T {
	int suma, minSuf;

	T() {
		suma = 0;
		minSuf = INF;
	}
	
	T(int x) {
		suma = x;
		minSuf = x;
	}
	
	T(int a, int b) {
		suma = a;
		minSuf = b;
	}
};

struct Seg {
	T ID = T(0, INF);
	T comb(T a, T b) {
		T w;
		w.suma = a.suma + b.suma;
		w.minSuf = min(b.minSuf, b.suma+a.minSuf);
		return w;
	}
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n, ID); }
	void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
	void upd(int p, int val) {
		seg[p+=n] = T(val);
		for(p/=2; p; p/=2) pull(p);
	}
	int query(int l, int r) {
		T ra = ID, rb = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2) {
			if(l&1) ra = comb(ra, seg[l++]);
			if(r&1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb).minSuf;
	}	
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string s;
	cin>>n>>s>>q;
	int a, b;
	vector<pi> qry[n];
	vector<int> ans(q, 0);
	Seg tree;
	tree.init(1<<20);
	for(int i=0; i<q; i++) {
		cin>>a>>b; a--; b--;
		qry[a].push_back({b, i});
	}
	for(int i=0; i<n; i++)
		tree.upd(i, 0);
	vector<int> ts;
	for(int l=n-1; l>=0; l--) {
		if(s[l] == 'T') ts.push_back(-l);
		else {
			if(!ts.empty()) {
				int x = ts[ts.size()-1];
				x*=-1;
				tree.upd(x, -1);
				ts.pop_back();
			}
			tree.upd(l, 1);
		}
		for(pi x : qry[l]) {
			int r = x.first;
			int i = x.second;
			auto it = lower_bound(ts.begin(), ts.end(), -r);
			//if(it == ts.end()) {
			//	cerr<<"SJdhsjdhsj\n";
			//}
			int cnt = (ts.end() - it);
			int minSuf = tree.query(l, r);
			int answer = cnt + max(0, -minSuf);
			ans[i] = answer;
			//cerr<<"! l = "<<l<<", r = "<<r<<", minSuf = "<<minSuf<<"\n";
		}
	}
	for(int i=0; i<q; i++)
		cout<<ans[i]<<"\n";
}

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