oj.uz

Submission #519533

# Submission time Handle Problem Language Result Execution time Memory
519533 2022-01-26T14:43:41 Z akhan42 Election (BOI18_election) C++17
100 / 100
 1818 ms 59008 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int INF = 1000 * 1000 * 1000;

struct Seg {
	int n;
	vi add, mn;

	Seg(int n, vi &vals): n(n) {
		add.assign(4 * n, 0);
		mn.assign(4 * n, 0);

		build(vals);
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr || add[v] == 0)
			return;

		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
		mn[2 * v] += add[v];
		mn[2 * v + 1] += add[v];
		add[v] = 0;
	}

	void pull(int v) {
		mn[v] = min(mn[2 * v], mn[2 * v + 1]);
	}

	void build(vi &vals, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			mn[v] = vals[tl];
			return;
		}
		int tm = (tl + tr) / 2;

		build(vals, 2 * v, tl, tm);
		build(vals, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return;

		if(tl == l && r == tr) {
			add[v] = val;
			mn[v] += val;
			return;
		}
		int tm = (tl + tr) / 2;

		update(l, min(r, tm), val, 2 * v, tl, tm);
		update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	int query(int l, int r, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return INF;

		if(tl == l && r == tr)
			return mn[v];
		int tm = (tl + tr) / 2;

		int ql = query(l, min(r, tm), 2 * v, tl, tm);
		int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);

		return min(ql, qr);
	}
};


void solve() {
	int n, q;
	string s;
	cin >> n >> s >> q;

	vii qs[n];
	forn(i, q) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		qs[r].eb(l, i);
	}

	vi pr(n);
	forn(i, n) {
		pr[i] = (s[i] == 'C' ? 1 : -1);
		if(i)
			pr[i] += pr[i - 1];
	}

	Seg sg_pr(n, pr);
	ordered_set turned_off;
	vi ans(q);

	forn(r, n) {
		if(s[r] == 'T') {
			turned_off.insert(r);
			sg_pr.update(r, n - 1, +1);
		} else if(sz(turned_off)) {
			int w = *turned_off.rbegin();
			turned_off.erase(w);

			sg_pr.update(w, n - 1, -1);
		}
		for(ii li: qs[r]) {
			int l = li.F, i = li.S;

			int pr_add = -(l ? sg_pr.query(l - 1, l - 1) : 0);
			sg_pr.update(l, r, pr_add);

			int mn = sg_pr.query(l, r);
			int rem = sz(turned_off) - turned_off.order_of_key(l);
			ans[i] = -min(0, mn) + rem;

			sg_pr.update(l, r, -pr_add);
		}
	}

	for(int a: ans)
		cout << a << '\n';
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
//	cout.tie(nullptr);

//	freopen("optmilk.in", "r", stdin);
//	freopen("optmilk.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 432 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 432 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 182 ms 7304 KB Output is correct
7 Correct 162 ms 6944 KB Output is correct
8 Correct 162 ms 6924 KB Output is correct
9 Correct 140 ms 7232 KB Output is correct
10 Correct 161 ms 7088 KB Output is correct
11 Correct 180 ms 8000 KB Output is correct
12 Correct 175 ms 7620 KB Output is correct
13 Correct 189 ms 8596 KB Output is correct
14 Correct 169 ms 7596 KB Output is correct
15 Correct 152 ms 7336 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 432 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 182 ms 7304 KB Output is correct
7 Correct 162 ms 6944 KB Output is correct
8 Correct 162 ms 6924 KB Output is correct
9 Correct 140 ms 7232 KB Output is correct
10 Correct 161 ms 7088 KB Output is correct
11 Correct 180 ms 8000 KB Output is correct
12 Correct 175 ms 7620 KB Output is correct
13 Correct 189 ms 8596 KB Output is correct
14 Correct 169 ms 7596 KB Output is correct
15 Correct 152 ms 7336 KB Output is correct
16 Correct 1541 ms 51260 KB Output is correct
17 Correct 1343 ms 48304 KB Output is correct
18 Correct 1514 ms 49440 KB Output is correct
19 Correct 1190 ms 51144 KB Output is correct
20 Correct 1439 ms 50216 KB Output is correct
21 Correct 1818 ms 56720 KB Output is correct
22 Correct 1510 ms 53332 KB Output is correct
23 Correct 1667 ms 59008 KB Output is correct
24 Correct 1551 ms 55032 KB Output is correct
25 Correct 1402 ms 51916 KB Output is correct