Submission #1264890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264890		SDAdzs1tg	Election (BOI18_election)	C++20	0 / 100	8 ms	12352 KiB

election

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 1;
int pre[maxn], st[maxn * 4], suff[maxn];
int mn[maxn * 4], ans[maxn];
struct p{
    int r, id;
};
void build(int id, int l, int r) {
    if(l == r) {
        mn[id] = suff[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    mn[id] = min(mn[id * 2], mn[id * 2 + 1]);
}
int getmin(int id, int l, int r, int u, int v) {
    if(r < u || v < l) return 1e18;
    if(u <= l && r <= v) return mn[id];
    int mid = (l + r) / 2;
    return min(getmin(id * 2, l, mid, u, v), getmin(id * 2 + 1, mid + 1, r, u, v));
}
void update(int id, int l, int r, int u, int v) {
    if(l == r && l == u) {
        st[id] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(u > mid) {
        update(id * 2 + 1, mid + 1, r, u, v);
    }
    else update(id * 2, l, mid, u, v);
    st[id] = st[id * 2] + st[id * 2 + 1];
}
int get(int id, int l, int r, int u, int v) {
    if(r < u || v < l) return 0;
    if(u <= l && r <= v) return st[id];
    int mid = (l + r) / 2;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
vector<p> q[maxn];
bool cmp(p a, p b) {
    return a.r < b.r;
}
signed main () {
    int n; cin >> n;
    string s; cin >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1];
        if(s[i] == 'C') pre[i]++;
        else pre[i]--;
    }
    int t; cin >> t;
    for(int i = 1; i <= t; i++){
        int l, r; cin >> l >> r;
        q[l].push_back({r, i});
    }
    for(int i = 1; i <= n; i++) {
        sort(q[i].begin(), q[i].end(), cmp);
    }
    stack<int> st;
    for(int i = n; i >= 1; i--) {
        while(!st.empty() && pre[st.top()] >= pre[i]) st.pop();
        if(!st.empty() && pre[st.top()] < 0) {
            update(1, 1, n, st.top(), 1);
        }
        st.push(i);
    }
    for(int i = 1; i <= n; i++) {
        if(get(1, 1, n, i, i)) {
            s[i] = '0';
        }
    }
//    cout << s << "\n";
    for(int i = n; i >= 1; i--) {
        suff[i] = suff[i + 1];
        if(s[i] == 'C') suff[i]++;
        else if(s[i] == 'T') suff[i]--;
    }
//    for(int i = 1; i <= n; i++) {
//    	cout << get(1, 1, n, i, i) << ' ';
//	}
//	cout << "\n";
//	for(int i = 1; i <= n; i++) {
//		cout << suff[i] << ' ';
//	}
//	cout << "\n";
    build(1, 1, n);
    for(int l = 1; l <= n; l++) {
        for(auto r : q[l]) {
            ans[r.id] = get(1, 1, n, l, r.r) + suff[r.r + 1] - getmin(1, 1, n, l, r.r);
            if(r.id == 1) {
            	//cout << suff[r.r + 1] << ' ' << getmin(1, 1, n, l, r.r) <<" aa\n";
			}
        }
    }
    for(int i = 1; i <= t; i++) {
    	cout << ans[i] << "\n";
	}
}

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