제출 #254209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254209		shayan_p	Election (BOI18_election)	C++14	100 / 100	1682 ms	53720 KiB

election

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 5e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<pii> qu[maxn];
int ans[maxn];

struct segment{
    int mn[4 * maxn], lz[4 * maxn], sm[4 * maxn];
    void shift(int l, int r, int id){
	mn[id]+= lz[id];
	sm[id]+= (r-l) * lz[id];
	if(r-l > 1)
	    lz[2*id]+= lz[id], lz[2*id+1]+= lz[id];
	lz[id] = 0;
    }
    void add(int f, int s, int x, int l = 0, int r = maxn, int id = 1){
	if(f >= s || l >= r)
	    return;
	shift(l, r, id);
	if(s <= l || r <= f)
	    return;
	if(f <= l && r <= s){
	    lz[id] = x;
	    shift(l, r, id);
	    return;
	}
	int mid = (l+r) >> 1;
	add(f, s, x, l, mid, 2*id);
	add(f, s, x, mid, r, 2*id+1);
	mn[id] = min(mn[2 * id], mn[2 * id + 1]);
	sm[id] = sm[2*id] + sm[2*id+1];
    }
    int askmn(int f, int s, int l = 0, int r = maxn, int id = 1){
	if(f >= s || l >= r)
	    return inf;
	shift(l, r, id);
	if(s <= l || r <= f)
	    return inf;
	if(f <= l && r <= s)
	    return mn[id];
	int mid = (l+r) >> 1;
	return min(askmn(f, s, l, mid, 2*id), askmn(f, s, mid, r, 2*id+1) );
    }
    int asksm(int f, int s, int l = 0, int r = maxn, int id = 1){
	if(f >= s || l >= r)
	    return 0;
	shift(l, r, id);
	if(s <= l || r <= f)
	    return 0;
	if(f <= l && r <= s)
	    return sm[id];
	int mid = (l+r) >> 1;
	return asksm(f, s, l, mid, 2*id) + asksm(f, s, mid, r, 2*id+1);
    }
};segment seg1, seg2;

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

    int n;
    cin >> n;
    string s;
    cin >> s;
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
	int l, r;
	cin >> l >> r;
	--l;
	qu[l].PB({r, i});
    }
    priority_queue<int, vector<int>, greater<int> > pq;
    for(int i = n-1; i >= 0; i--){
	if(s[i] == 'C'){
	    seg1.add(0, i + 1, 1);
	    if(!pq.empty()){
		seg2.add(pq.top(), pq.top() + 1, -1);
		seg1.add(0, pq.top() + 1, -1);
		pq.pop();
	    }
	}
	else{	    
	    seg2.add(i, i+1, 1);
	    pq.push(i);
	}
	for(pii p : qu[i]){
	    ans[p.S] = seg2.asksm(i, p.F) - min(int(0), (seg1.askmn(i, p.F) - seg1.askmn(p.F, p.F + 1)));
	}
    }
    for(int i = 0; i < q; i++){
	cout << ans[i] << "\n";
    }
    return 0;
}

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