oj.uz

답안 #642198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642198 2022-09-18T20:55:54 Z eyangch Election (BOI18_election) C++17
0 / 100
 19 ms 43476 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define eat cin
#define moo cout
#define int long long

using namespace std;
using namespace __gnu_pbds;

struct segtree{
	int A[2000005], S[2000005];
	void init(){
		fill(A, A+2000005, 0);
		fill(S, S+2000005, 0);
	}
	void upd(int i, int x, int l=0, int r=499999, int v=1){
		if(l > i || r < i) return;
		if(l == r){
			A[v] = min(x, 0LL);
			S[v] = x;
			return;
		}
		upd(i, x, l, (l+r)/2, v*2);
		upd(i, x, (l+r)/2+1, r, v*2+1);
		S[v] = S[v*2] + S[v*2+1];
		A[v] = min(A[v*2], S[v*2] + A[v*2+1]);
	}
	pair<int, int> qry(int i, int l=0, int r=499999, int v=1){
		if(r < i) return {0, 0};
		if(l >= i){
			return {A[v], S[v]};
		}
		pair<int, int> q1 = qry(i, l, (l+r)/2, v*2);
		pair<int, int> q2 = qry(i, (l+r)/2+1, r, v*2+1);
		int c1 = q1.second + q2.first;
		int c2 = q1.first;
		return {min(c1, c2), q1.second + q2.second};
	}
};

int N, Q, ans[500000];
string S;
pair<int, int> A[500000];
vector<int> W[500000];
segtree segt;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

int32_t main(){
	eat.tie(0) -> sync_with_stdio(0);
	eat >> N >> S >> Q;
	for(int i = 0; i < Q; i++){
		eat >> A[i].first >> A[i].second;
		A[i].first--, A[i].second--;
		W[A[i].second].push_back(i);
	}
	segt.init();
	stack<int> st;
	for(int i = 0; i < N; i++){
		if(S[i] == 'T'){
			oset.insert(i);
			st.push(i);
		}
		if(S[i] == 'C'){
			if(!st.empty()){
				int x = st.top();
				st.pop();
				oset.erase(x);
				segt.upd(x, -1);
			}
			segt.upd(i, 1);
		}
		for(int j : W[i]){
			int q = segt.qry(A[j].first).first;
			ans[j] = q + (st.size() - oset.order_of_key(A[j].first));
		}
	}
	for(int i = 0; i < Q; i++){
		moo << ans[i] << endl;
	}
}

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 43476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 43476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 43476 KB Output isn't correct
2 Halted 0 ms 0 KB -