oj.uz

Submission #365306

# Submission time Handle Problem Language Result Execution time Memory
365306 2021-02-11T12:16:39 Z dynam1c Election (BOI18_election) C++17
100 / 100
 1073 ms 52580 KB 
//#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 107 ms 7424 KB Output is correct
7 Correct 95 ms 7020 KB Output is correct
8 Correct 98 ms 7020 KB Output is correct
9 Correct 103 ms 7276 KB Output is correct
10 Correct 104 ms 7168 KB Output is correct
11 Correct 112 ms 7512 KB Output is correct
12 Correct 107 ms 7424 KB Output is correct
13 Correct 100 ms 7532 KB Output is correct
14 Correct 107 ms 7404 KB Output is correct
15 Correct 107 ms 7336 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 107 ms 7424 KB Output is correct
7 Correct 95 ms 7020 KB Output is correct
8 Correct 98 ms 7020 KB Output is correct
9 Correct 103 ms 7276 KB Output is correct
10 Correct 104 ms 7168 KB Output is correct
11 Correct 112 ms 7512 KB Output is correct
12 Correct 107 ms 7424 KB Output is correct
13 Correct 100 ms 7532 KB Output is correct
14 Correct 107 ms 7404 KB Output is correct
15 Correct 107 ms 7336 KB Output is correct
16 Correct 1057 ms 50756 KB Output is correct
17 Correct 857 ms 47980 KB Output is correct
18 Correct 966 ms 49132 KB Output is correct
19 Correct 887 ms 50756 KB Output is correct
20 Correct 1035 ms 49900 KB Output is correct
21 Correct 1073 ms 52196 KB Output is correct
22 Correct 1041 ms 51740 KB Output is correct
23 Correct 1033 ms 52580 KB Output is correct
24 Correct 1047 ms 51812 KB Output is correct
25 Correct 1051 ms 51052 KB Output is correct