Submission #1123329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123329		liemdinat	Election (BOI18_election)	C++20	0 / 100	1 ms	320 KiB

election

#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FORD(i, k, n) for(int i = k; i >= n; i--)
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPD(i, n) for(int i = n - 1; i >= 0; i--)
#define ii pair<int,int>
#define trii pair<int,ii>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define all(x, n) (x) + 1, (x) + n + 1
#define allv(x) (x).begin(), (x).end()
#define vii vector<ii>
#define sz(x) ((int)x.size())

using namespace std;
const int N = 5e5 + 5;
int a[N];

struct Node
{
	int lef[3], tot[3];
	Node(){};
	Node(int x)
	{
		if (x == 0) lef[0] = lef[1] = 1, tot[0] = tot[1] = tot[2] = 0;
		else if (x == 1) lef[0] = lef[1] = 0, tot[0] = tot[1] = tot[2] = 1;
		else lef[0] = -1;
		lef[2] = 1;
	}
	friend Node combine(const Node &x, const Node &y)
	{
		Node ans;
		if (x.lef[0] == -1) return y;
		if (y.lef[0] == -1) return x;
		int conrig = max(y.tot[0] - x.lef[0], 0);
		int conlef = max(x.tot[1] - y.lef[1], 0);
		ans.tot[0] = x.tot[0] + conrig;
		ans.lef[0] = y.lef[0] + y.tot[0] - conrig;
		ans.tot[1] = y.tot[1] + conlef;
		ans.lef[1] = x.lef[1] + x.tot[1] - conlef;
		ans.lef[2] = x.lef[2] + y.lef[2];
		ans.tot[2] = max(x.tot[0], conlef) + max(y.tot[1], conrig);
		return ans;
	}
};

struct SegmentTree
{
	int n;
	Node st[N<<2];
	void build(int _n)
	{
		n = _n;
		run(1, n, 1);
	}
	void run(int l, int r, int i)
	{
		if (l == r)
		{
			st[i] = Node(a[l]);
			return;
		}
		int mid = (l+r) >> 1;
		run(l, mid, i<<1);
		run(mid+1, r, i<<1|1);
		st[i] = combine(st[i<<1], st[i<<1|1]);
	}
	Node query(int l, int r, int u, int v, int i)
	{
		if (u <= l && r <= v)
		{
			return st[i];
		}
		if (r < u || v < l) return Node(-1);
		int mid = (l+r) >> 1;
		return combine(query(l, mid, u, v, i<<1), query(mid+1, r, u, v, i<<1|1));
	}
	int getlr(int l, int r)
	{
		return query(1, n, l, r, 1).tot[2];
	}
} myIT;

int32_t main()
{
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    FOR(i, 1, n)
    {
    	char x; cin >> x;
    	if (x == 'C') a[i] = 0;
    	else a[i] = 1;
    }
    myIT.build(n);
    int q; cin >> q;
    FOR(i, 1, q)
    {
    	int l, r; cin >> l >> r;
    	cout << myIT.getlr(l, r) << '\n';
    }
    return 0;
}

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