Submission #365306

#	Time	Username	Problem	Language	Result	Execution time	Memory
365306		dynam1c	Election (BOI18_election)	C++17	100 / 100	1073 ms	52580 KiB

election

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// if you're reading this i hope to meet you in IOI 2021
// RECHECK CONSTRAINTS AFTER MAKING A REDUCTION

struct Segtree {
	int n; 
	vector<int> seg, lazy;
	Segtree(int n) : n(n), seg(4*n), lazy(4*n) {}
	void build(vector<int>& arr, int v, int vl, int vr) {
		if (vr-vl == 1)
			seg[v] = arr[vl];
		else {
			int vm = vl+vr>>1;
			build(arr, v<<1, vl, vm);
			build(arr, v<<1|1, vm, vr);
			seg[v] = min(seg[v<<1], seg[v<<1|1]);
		}
	}
	void build(vector<int>& arr) {
		build(arr, 1, 0, n);
	}
	void push(int v) {
		seg[v<<1] += lazy[v];
		lazy[v<<1] += lazy[v];
		seg[v<<1|1] += lazy[v];
		lazy[v<<1|1] += lazy[v];
		lazy[v] = 0;
	}
	void update(int v, int vl, int vr, int l, int r, int x) {
		if (l >= r) return;
		if (l == vl and r == vr)
			seg[v] += x, lazy[v] += x;
		else {
			push(v);
			int vm = vl+vr>>1;
			update(v<<1, vl, vm, l, min(r, vm), x);
			update(v<<1|1, vm, vr, max(l, vm), r, x);
			seg[v] = min(seg[v<<1], seg[v<<1|1]);
		}
	}
	void update(int l, int r, int x) {
		update(1, 0, n, l, r, x);
	}
	int query(int v, int vl, int vr, int l, int r) {
		if (l >= r) return INT_MAX;
		if (l <= vl and vr <= r) return seg[v];
		push(v);
		int vm = vl+vr>>1;
		return min(query(v<<1, vl, vm, l, min(r, vm)), query(v<<1|1, vm, vr, max(l, vm), r));
	}
	int query(int l, int r) {
		return query(1, 0, n, l, r);
	}
};

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		arr[i] = (c == 'C' ? 1 : -1);
	}
	cin >> q;
	vector<int> res(q);
	vector<vector<array<int, 2>>> qs(n+1);
	Segtree rmq(n+1); // [i] = balance after i elements, RMQ and range add update
	for (int qq = 0; qq < q; qq++) {
		int l, r;
		cin >> l >> r; l--;
		qs[r].push_back({l, qq});
	}
	vector<int> ts;
	for (int r = 0; r <= n; r++) {
		for (auto [l, qq] : qs[r]) {
			res[qq] = rmq.query(l, l+1) - rmq.query(l, r+1) + (ts.end() - lower_bound(all(ts), l));
		}

		if (r < n) {
			if (arr[r] == -1)
				ts.push_back(r);
			else {
				if (ts.size())
					rmq.update(ts.back()+1, n+1, -1), ts.pop_back();
				rmq.update(r+1, n+1, 1);
			}
		}
	}
	for (int e : res) cout << e << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Compilation message (stderr)

election.cpp: In member function 'void Segtree::build(std::vector<int>&, int, int, int)':
election.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |    int vm = vl+vr>>1;
      |             ~~^~~
election.cpp: In member function 'void Segtree::update(int, int, int, int, int, int)':
election.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    int vm = vl+vr>>1;
      |             ~~^~~
election.cpp: In member function 'int Segtree::query(int, int, int, int, int)':
election.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int vm = vl+vr>>1;
      |            ~~^~~

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