oj.uz

답안 #612604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612604 2022-07-29T18:10:46 Z amunduzbaev Election (BOI18_election) C++17
100 / 100
 648 ms 47448 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;

const int N = 5e5 + 5;

struct ST{
	ar<int, 2> tree[N << 2];
	ar<int, 2> merge(ar<int, 2>& a, ar<int, 2>& b){
		ar<int, 2> c {};
		c[0] = a[0] + b[0];
		c[1] = max(b[1], b[0] + a[1]);
		return c;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x][0] = v, tree[x][1] = max(0, v);
			return;
		} int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
	}
	ar<int, 2> ans;
	
	void get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			ans = merge(ans, tree[x]);
			return;
		} int m = (lx + rx) >> 1;
		get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1);
	}
}tree;

int l[N], r[N], res[N];
vector<int> Q[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	string s; cin >> s;
	int q; cin >> q;
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i]; r[i]--;
		Q[--l[i]].push_back(i);
	}
	
	deque<int> t;
	for(int i=n-1;~i;i--){
		if(s[i] == 'T'){
			t.push_front(i);
		} else {
			tree.set(i, -1);
			if(!t.empty()) tree.set(t.front(), 1), t.pop_front();
		}
		
		for(auto j : Q[i]){
			int c = upper_bound(t.begin(), t.end(), r[j]) - t.begin();
			tree.ans = {0, 0};
			tree.get(i, r[j]);
			res[j] = c + tree.ans[1];
		}
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 9 ms 12212 KB Output is correct
4 Correct 10 ms 12196 KB Output is correct
5 Correct 8 ms 12184 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 9 ms 12212 KB Output is correct
4 Correct 10 ms 12196 KB Output is correct
5 Correct 8 ms 12184 KB Output is correct
6 Correct 60 ms 16776 KB Output is correct
7 Correct 50 ms 15896 KB Output is correct
8 Correct 55 ms 16144 KB Output is correct
9 Correct 53 ms 16604 KB Output is correct
10 Correct 54 ms 16552 KB Output is correct
11 Correct 64 ms 16844 KB Output is correct
12 Correct 62 ms 16852 KB Output is correct
13 Correct 62 ms 16744 KB Output is correct
14 Correct 57 ms 16792 KB Output is correct
15 Correct 55 ms 16744 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 9 ms 12212 KB Output is correct
4 Correct 10 ms 12196 KB Output is correct
5 Correct 8 ms 12184 KB Output is correct
6 Correct 60 ms 16776 KB Output is correct
7 Correct 50 ms 15896 KB Output is correct
8 Correct 55 ms 16144 KB Output is correct
9 Correct 53 ms 16604 KB Output is correct
10 Correct 54 ms 16552 KB Output is correct
11 Correct 64 ms 16844 KB Output is correct
12 Correct 62 ms 16852 KB Output is correct
13 Correct 62 ms 16744 KB Output is correct
14 Correct 57 ms 16792 KB Output is correct
15 Correct 55 ms 16744 KB Output is correct
16 Correct 527 ms 46272 KB Output is correct
17 Correct 355 ms 39860 KB Output is correct
18 Correct 451 ms 42420 KB Output is correct
19 Correct 415 ms 44560 KB Output is correct
20 Correct 495 ms 45228 KB Output is correct
21 Correct 648 ms 47448 KB Output is correct
22 Correct 542 ms 46952 KB Output is correct
23 Correct 552 ms 46108 KB Output is correct
24 Correct 575 ms 46316 KB Output is correct
25 Correct 591 ms 46332 KB Output is correct