oj.uz

답안 #321179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321179 2020-11-11T11:45:02 Z kapsel Election (BOI18_election) C++17
0 / 100
 13 ms 16876 KB 
#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

typedef pair<int, int> pi;

const int INF = 1e9 + 2137;

struct T {
	int suma, minSuf;

	T() {
		suma = 0;
		minSuf = INF;
	}
	
	T(int x) {
		suma = x;
		minSuf = x;
	}
	
	T(int a, int b) {
		suma = a;
		minSuf = b;
	}
};

struct Seg {
	T ID = T(0, INF);
	T comb(T a, T b) {
		T w;
		w.suma = a.suma + b.suma;
		w.minSuf = min(b.minSuf, b.suma+a.minSuf);
		return w;
	}
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n, ID); }
	void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
	void upd(int p, int val) {
		seg[p+=n] = T(val);
		for(p/=2; p; p/=2) pull(p);
	}
	int query(int l, int r) {
		T ra = ID, rb = ID;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2) {
			if(l&1) ra = comb(ra, seg[l++]);
			if(r&1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb).minSuf;
	}	
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string s;
	cin>>n>>s>>q;
	int a, b;
	vector<pi> qry[n];
	vector<int> ans(q, 0);
	Seg tree;
	tree.init(1<<20);
	for(int i=0; i<q; i++) {
		cin>>a>>b; a--; b--;
		qry[a].push_back({b, i});
	}
	for(int i=0; i<n; i++)
		tree.upd(i, 0);
	vector<int> ts;
	for(int l=n-1; l>=0; l--) {
		if(s[l] == 'T') ts.push_back(l);
		else {
			if(!ts.empty()) {
				int x = ts[ts.size()-1];
				tree.upd(x, -1);
				ts.pop_back();
			}
			tree.upd(l, 1);
		}
		for(pi x : qry[l]) {
			int r = x.first;
			int i = x.second;
			auto it = upper_bound(ts.begin(), ts.end(), r);
			int cnt = (int) ts.size() - (ts.end() - it);
			int minSuf = tree.query(l, r);
			int answer = cnt + max(0, -minSuf);
			ans[i] = answer;
			//cerr<<"! l = "<<l<<", r = "<<r<<", minSuf = "<<minSuf<<"\n";
		}
	}
	for(int i=0; i<q; i++)
		cout<<ans[i]<<"\n";
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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