oj.uz

Submission #254209

# Submission time Handle Problem Language Result Execution time Memory
254209 2020-07-29T14:33:41 Z shayan_p Election (BOI18_election) C++14
100 / 100
 1682 ms 53720 KB 
// 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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12544 KB Output is correct
2 Correct 13 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 13 ms 12544 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12544 KB Output is correct
2 Correct 13 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 13 ms 12544 KB Output is correct
6 Correct 171 ms 17912 KB Output is correct
7 Correct 153 ms 17528 KB Output is correct
8 Correct 159 ms 17528 KB Output is correct
9 Correct 180 ms 17872 KB Output is correct
10 Correct 184 ms 17784 KB Output is correct
11 Correct 239 ms 18168 KB Output is correct
12 Correct 190 ms 18044 KB Output is correct
13 Correct 188 ms 18296 KB Output is correct
14 Correct 184 ms 18040 KB Output is correct
15 Correct 155 ms 17912 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12544 KB Output is correct
2 Correct 13 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 14 ms 12544 KB Output is correct
5 Correct 13 ms 12544 KB Output is correct
6 Correct 171 ms 17912 KB Output is correct
7 Correct 153 ms 17528 KB Output is correct
8 Correct 159 ms 17528 KB Output is correct
9 Correct 180 ms 17872 KB Output is correct
10 Correct 184 ms 17784 KB Output is correct
11 Correct 239 ms 18168 KB Output is correct
12 Correct 190 ms 18044 KB Output is correct
13 Correct 188 ms 18296 KB Output is correct
14 Correct 184 ms 18040 KB Output is correct
15 Correct 155 ms 17912 KB Output is correct
16 Correct 1682 ms 51876 KB Output is correct
17 Correct 1227 ms 48396 KB Output is correct
18 Correct 1436 ms 49112 KB Output is correct
19 Correct 1314 ms 50644 KB Output is correct
20 Correct 1590 ms 50844 KB Output is correct
21 Correct 1558 ms 53624 KB Output is correct
22 Correct 1472 ms 53028 KB Output is correct
23 Correct 1507 ms 53720 KB Output is correct
24 Correct 1486 ms 53140 KB Output is correct
25 Correct 1514 ms 52232 KB Output is correct