oj.uz

Submission #1050465

# Submission time Handle Problem Language Result Execution time Memory
1050465 2024-08-09T09:54:36 Z vako_p Election (BOI18_election) C++14
100 / 100
 483 ms 44744 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 5e5 + 5;
ll n,qq,ans[mxN];
pair<ll,pair<ll,ll>> q[mxN];
char ch[mxN];

struct segtree{
	vector<ll> v,v1;
	ll sz = 1;
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, 0LL);
		v1.assign(2 * sz, 0LL);
	}
	
	void set(ll val, ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return;
		if(lx >= l and rx <= r){
			v1[x] += val;
			v[x] += val;
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		set(val, l, r, 2 * x + 1, lx, mid);
		set(val, l, r, 2 * x + 2, mid, rx);
		v[x] = min(v[2 * x + 1], v[2 * x + 2]) + v1[x]; 
	}
	
	void set(ll val, ll l, ll r){
		set(val, l, r, 0, 0, sz);
	}
	
	ll find(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return 1e16;
		if(lx >= l and rx <= r) return v[x];
		ll mid = lx + (rx - lx) / 2;
		return (min(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx)) + v1[x]);
	}
	
	ll find(ll l, ll r){
		return find(l, r, 0, 0, sz);	
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	segtree s;
	s.init();
	for(int i = 0; i < n; i++){
		cin >> ch[i];
	}
	cin >> qq;
	for(int i = 0; i < qq; i++){
		cin >> q[i].second.first >> q[i].first;
		q[i].first--;
		q[i].second.first--;
		q[i].second.second = i; 
	}
	sort(q, q + qq);
	vector<ll> st;
	ll l1 = 0;
	for(int i = 0; i < qq; i++){
		ll l = q[i].second.first, r = q[i].first;
//		cout << l << ' ' << r << '\n';
		while(l1 <= r){
			if(ch[l1] == 'T') st.pb(l1);
			else{
				s.set(1, l1, n);
				if(!st.empty()){
					s.set(-1, st[st.size() - 1], n);
					st.pop_back(); 
				}
			}
			l1++;
//			cout << l1 << '\n';
		}
		ll x,sz = st.size();
		auto it = lower_bound(st.begin(), st.end(), l);
		if(it == st.end()) x = 0;
	 	else x = sz - (it - st.begin());
//		cout << s.find(l - 1, l) << '\n';
		if(l) ans[q[i].second.second] = max(0LL, -(s.find(l, r) - s.find(l - 1, l))) + x;
		else ans[q[i].second.second] = max(0LL, -(s.find(l, r))) + x;
	}
	for(int i = 0; i < qq; i++) cout << ans[i] << '\n';
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 47 ms 11860 KB Output is correct
7 Correct 45 ms 11928 KB Output is correct
8 Correct 50 ms 11732 KB Output is correct
9 Correct 42 ms 11860 KB Output is correct
10 Correct 45 ms 11864 KB Output is correct
11 Correct 48 ms 12112 KB Output is correct
12 Correct 47 ms 12112 KB Output is correct
13 Correct 79 ms 12264 KB Output is correct
14 Correct 44 ms 12112 KB Output is correct
15 Correct 46 ms 12008 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 47 ms 11860 KB Output is correct
7 Correct 45 ms 11928 KB Output is correct
8 Correct 50 ms 11732 KB Output is correct
9 Correct 42 ms 11860 KB Output is correct
10 Correct 45 ms 11864 KB Output is correct
11 Correct 48 ms 12112 KB Output is correct
12 Correct 47 ms 12112 KB Output is correct
13 Correct 79 ms 12264 KB Output is correct
14 Correct 44 ms 12112 KB Output is correct
15 Correct 46 ms 12008 KB Output is correct
16 Correct 437 ms 42520 KB Output is correct
17 Correct 372 ms 42060 KB Output is correct
18 Correct 409 ms 42320 KB Output is correct
19 Correct 438 ms 41812 KB Output is correct
20 Correct 462 ms 41760 KB Output is correct
21 Correct 462 ms 44328 KB Output is correct
22 Correct 460 ms 43696 KB Output is correct
23 Correct 382 ms 44744 KB Output is correct
24 Correct 465 ms 43924 KB Output is correct
25 Correct 483 ms 43000 KB Output is correct