Submission #565597

#	Time	Username	Problem	Language	Result	Execution time	Memory
565597		haxorman	Election (BOI18_election)	C++14	0 / 100	4 ms	340 KiB

election

#include <bits/stdc++.h>
using namespace std;

#define int long long
 
const int mxN = 5e5 + 7;
const int SZ = 1 << (int) ceil(log2(mxN));
 
int seg[2 * SZ], Left, Right, pos, val;
 
int combine(int a, int b) {
	return a + b;
}
 
void update() {
    int ind = pos + SZ - 1;
    seg[ind] = val;
    
    for (ind /= 2; ind; ind /= 2) {
        seg[ind] = combine(seg[2 * ind], seg[2 * ind + 1]);
    }
}
 
int query(int ind = 1, int l = 1, int r = SZ) {
    if (r < Left || l > Right) {
        return 0;
    }
    
    if (Left <= l && r <= Right) {
        return seg[ind];
    }
    
    int mid = (l + r) / 2;
    return combine(query(2 * ind, l, mid), query(2 * ind + 1, mid + 1, r));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n;
	string s;
	cin >> n >> s;

	for (pos = 1; pos <= n; ++pos) {
		if (s[pos - 1] == 'T') {
			val = 1;
		}
		else {
			val = 0;
		}

		update();
	}
	
	int q;
	cin >> q;

	while (q--) {
		int l, r;
		cin >> l >> r;
		
		Left = l;
		int lb = l, rb = r, ans = l - 1;
		while (lb <= rb) {
			int mb = (lb + rb) / 2;
			Right = mb;

			int cnt = query();
			if (!cnt) {
				lb = mb + 1;
				ans = mb;
			}
			else {
				rb = mb - 1;
			}
		}
		
		Left = ans + 1;
		Right = r;
		
		int num = Right - Left + 1;
		int ts = query();
		cout << ts - num + ts << "\n";
	}
}

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