oj.uz

Submission #321273

# Submission time Handle Problem Language Result Execution time Memory
321273 2020-11-11T19:53:14 Z kapsel Election (BOI18_election) C++17
100 / 100
 584 ms 53104 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];
				x*=-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 = lower_bound(ts.begin(), ts.end(), -r);
			//if(it == ts.end()) {
			//	cerr<<"SJdhsjdhsj\n";
			//}
			int cnt = (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
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16876 KB Output is correct
2 Correct 12 ms 16876 KB Output is correct
3 Correct 12 ms 16876 KB Output is correct
4 Correct 12 ms 16876 KB Output is correct
5 Correct 12 ms 16876 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16876 KB Output is correct
2 Correct 12 ms 16876 KB Output is correct
3 Correct 12 ms 16876 KB Output is correct
4 Correct 12 ms 16876 KB Output is correct
5 Correct 12 ms 16876 KB Output is correct
6 Correct 66 ms 21604 KB Output is correct
7 Correct 58 ms 20964 KB Output is correct
8 Correct 59 ms 21092 KB Output is correct
9 Correct 73 ms 21332 KB Output is correct
10 Correct 64 ms 21348 KB Output is correct
11 Correct 69 ms 21604 KB Output is correct
12 Correct 67 ms 21604 KB Output is correct
13 Correct 69 ms 21776 KB Output is correct
14 Correct 66 ms 21604 KB Output is correct
15 Correct 64 ms 21476 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16876 KB Output is correct
2 Correct 12 ms 16876 KB Output is correct
3 Correct 12 ms 16876 KB Output is correct
4 Correct 12 ms 16876 KB Output is correct
5 Correct 12 ms 16876 KB Output is correct
6 Correct 66 ms 21604 KB Output is correct
7 Correct 58 ms 20964 KB Output is correct
8 Correct 59 ms 21092 KB Output is correct
9 Correct 73 ms 21332 KB Output is correct
10 Correct 64 ms 21348 KB Output is correct
11 Correct 69 ms 21604 KB Output is correct
12 Correct 67 ms 21604 KB Output is correct
13 Correct 69 ms 21776 KB Output is correct
14 Correct 66 ms 21604 KB Output is correct
15 Correct 64 ms 21476 KB Output is correct
16 Correct 553 ms 51448 KB Output is correct
17 Correct 393 ms 47224 KB Output is correct
18 Correct 467 ms 48320 KB Output is correct
19 Correct 466 ms 49892 KB Output is correct
20 Correct 522 ms 50468 KB Output is correct
21 Correct 584 ms 52856 KB Output is correct
22 Correct 543 ms 52280 KB Output is correct
23 Correct 566 ms 53104 KB Output is correct
24 Correct 533 ms 52444 KB Output is correct
25 Correct 526 ms 51704 KB Output is correct