oj.uz

Submission #568760

# Submission time Handle Problem Language Result Execution time Memory
568760 2022-05-26T07:29:36 Z ngpin04 Election (BOI18_election) C++17
100 / 100
 586 ms 57196 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 5e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct segtree {
	struct node {
		int sum, minr;

		node(int _sum = 0, int _minr = 0) {
			sum = _sum;
			minr = _minr;
		}	

		node operator + (const node &p) const {
			node res;
			res.sum = sum + p.sum;
			res.minr = min(p.minr, minr + p.sum);
			return res;
		}
	};

	int n;
	vector <node> st;

	segtree(int _n = 0) {
		n = _n;
		st.assign(4 * n + 5, node());
	}

	void update(int id, int l, int r, int pos, int val) {
		if (l > pos || r < pos)
			return;
		if (l == r) {
			st[id] = node(val, val);
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, pos, val);
		update(id << 1 | 1, mid + 1, r, pos, val);
		st[id] = st[id << 1] + st[id << 1 | 1];
	}

	void update(int pos, int val) {
		update(1, 1, n, pos, val);
	}

	node getval(int id, int l, int r, int u, int v) {
		if (l > v || r < u)
			return node();
		if (l >= u && r <= v)
			return st[id];
		int mid = (l + r) >> 1;
		node lnode = getval(id << 1, l, mid, u, v);
		node rnode = getval(id << 1 | 1, mid + 1, r, u, v);
		return lnode + rnode;
	}

	int getval(int l, int r) {
		return getval(1, 1, n, l, r).minr;
	}
};

vector <int> qr[N];

int ans[N];
int bit[N];
int l[N];
int r[N];
int a[N];
int n, q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n;
	{
		string s; cin >> s;
		for (int i = 1; i <= n; i++)
			a[i] = (s[i - 1] == 'C') ? 1 : -1;
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> l[i] >> r[i];
		qr[l[i]].push_back(i);
	}

	segtree st(n);

	vector <int> pos;
	for (int i = n; i >= 1; i--) {
		if (a[i] < 0)
			pos.push_back(-i);	
		else {
			if (pos.size()) {
				st.update(-pos.back(), -1);
				pos.pop_back();
			}
			st.update(i, 1);
		} 	

		for (int ind : qr[i]) {
			int cntdel = (int) pos.size() - 
			(lower_bound(ALL(pos), -r[ind]) - pos.begin());
			ans[ind] = max(0, -st.getval(l[ind], r[ind])) + cntdel;
		}
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12220 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 8 ms 12216 KB Output is correct
5 Correct 8 ms 12244 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12220 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 8 ms 12216 KB Output is correct
5 Correct 8 ms 12244 KB Output is correct
6 Correct 62 ms 17992 KB Output is correct
7 Correct 49 ms 17032 KB Output is correct
8 Correct 54 ms 17300 KB Output is correct
9 Correct 57 ms 17760 KB Output is correct
10 Correct 59 ms 17836 KB Output is correct
11 Correct 62 ms 18164 KB Output is correct
12 Correct 58 ms 18008 KB Output is correct
13 Correct 67 ms 18248 KB Output is correct
14 Correct 65 ms 17996 KB Output is correct
15 Correct 57 ms 18016 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12220 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 8 ms 12216 KB Output is correct
5 Correct 8 ms 12244 KB Output is correct
6 Correct 62 ms 17992 KB Output is correct
7 Correct 49 ms 17032 KB Output is correct
8 Correct 54 ms 17300 KB Output is correct
9 Correct 57 ms 17760 KB Output is correct
10 Correct 59 ms 17836 KB Output is correct
11 Correct 62 ms 18164 KB Output is correct
12 Correct 58 ms 18008 KB Output is correct
13 Correct 67 ms 18248 KB Output is correct
14 Correct 65 ms 17996 KB Output is correct
15 Correct 57 ms 18016 KB Output is correct
16 Correct 547 ms 55036 KB Output is correct
17 Correct 393 ms 48740 KB Output is correct
18 Correct 462 ms 51144 KB Output is correct
19 Correct 434 ms 53368 KB Output is correct
20 Correct 547 ms 54248 KB Output is correct
21 Correct 586 ms 56808 KB Output is correct
22 Correct 547 ms 56200 KB Output is correct
23 Correct 560 ms 57196 KB Output is correct
24 Correct 528 ms 56564 KB Output is correct
25 Correct 524 ms 55484 KB Output is correct