oj.uz

Submission #87768

# Submission time Handle Problem Language Result Execution time Memory
87768 2018-12-02T11:28:14 Z memikakizaki Election (BOI18_election) C++14
100 / 100
 1155 ms 120588 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1 << 19;

class Elections {

	int n, q, ans[N];
	string s;
	vector<pair<int,int> > qq[N];

	int mn[2*N], lz[2*N];
	void apply(int i, int l, int r) {
		if(!lz[i]) return;
		mn[i] += lz[i];
		if(i < N) {
			lz[i << 1] += lz[i];
			lz[i << 1 | 1] += lz[i];
		}
		lz[i] = 0;
	}
	void update_mn(int tl, int tr, int v, int i = 1, int l = 0, int r = N-1) {
		apply(i, l, r);
		if(r < tl || l > tr) return;
		if(tl <= l && r <= tr) {
			lz[i] += v;
			apply(i, l, r);
			return;
		}
		int mid = l+r >> 1;
		update_mn(tl, tr, v, i << 1, l, mid);
		update_mn(tl, tr, v, i << 1 | 1, mid+1, r);
		mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
	}
	int query_mn(int tl, int tr, int i = 1, int l = 0, int r = N-1) {
		apply(i, l, r);
		if(r < tl || l > tr) return INF;
		if(tl <= l && r <= tr) return mn[i];
		int mid = l+r >> 1;
		return min(query_mn(tl, tr, i << 1, l, mid), query_mn(tl, tr, i << 1 | 1, mid+1, r));
	}

public:
	void run(istream &cin, ostream &cout) {
		cin >> n >> s >> q;
		for(int i = 0, l, r; i < q; i++) {
			cin >> l >> r;
			--l, --r;
			qq[r].emplace_back(l, i);
		}
		vector<int> ts;
		for(int i = 0; i < n; i++) {
			if(s[i] == 'T') ts.push_back(i);
			else {
				if(!ts.empty()) {
					update_mn(ts.back(), n-1, -1);
					ts.pop_back();
				}
				update_mn(i, n-1, 1);
			}
			for(auto p: qq[i]) {
				int j, qidx;
				tie(j, qidx) = p;
				int res = query_mn(j, i) - (j > 0 ? query_mn(j-1, j-1) : 0);
				auto it = lower_bound(ts.begin(), ts.end(), j);
				int cnt = (int) ts.size() - (it - ts.begin());
//				cout << qidx << ' ' << cnt << ' ' << res << endl;
				ans[qidx] = cnt - min(res, 0);
			}
		}
		for(int i = 0; i < q; i++) cout << ans[i] << '\n';
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    Elections *obj = new Elections();
		obj->run(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message

election.cpp: In member function 'void Elections::update_mn(int, int, int, int, int, int)':
election.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
             ~^~
election.cpp: In member function 'int Elections::query_mn(int, int, int, int, int)':
election.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
             ~^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23032 KB Output is correct
2 Correct 27 ms 23064 KB Output is correct
3 Correct 28 ms 23064 KB Output is correct
4 Correct 30 ms 23156 KB Output is correct
5 Correct 29 ms 23160 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23032 KB Output is correct
2 Correct 27 ms 23064 KB Output is correct
3 Correct 28 ms 23064 KB Output is correct
4 Correct 30 ms 23156 KB Output is correct
5 Correct 29 ms 23160 KB Output is correct
6 Correct 140 ms 25012 KB Output is correct
7 Correct 114 ms 25652 KB Output is correct
8 Correct 109 ms 26716 KB Output is correct
9 Correct 139 ms 27820 KB Output is correct
10 Correct 145 ms 28880 KB Output is correct
11 Correct 150 ms 30028 KB Output is correct
12 Correct 139 ms 30900 KB Output is correct
13 Correct 138 ms 32012 KB Output is correct
14 Correct 124 ms 32728 KB Output is correct
15 Correct 121 ms 33604 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23032 KB Output is correct
2 Correct 27 ms 23064 KB Output is correct
3 Correct 28 ms 23064 KB Output is correct
4 Correct 30 ms 23156 KB Output is correct
5 Correct 29 ms 23160 KB Output is correct
6 Correct 140 ms 25012 KB Output is correct
7 Correct 114 ms 25652 KB Output is correct
8 Correct 109 ms 26716 KB Output is correct
9 Correct 139 ms 27820 KB Output is correct
10 Correct 145 ms 28880 KB Output is correct
11 Correct 150 ms 30028 KB Output is correct
12 Correct 139 ms 30900 KB Output is correct
13 Correct 138 ms 32012 KB Output is correct
14 Correct 124 ms 32728 KB Output is correct
15 Correct 121 ms 33604 KB Output is correct
16 Correct 1074 ms 51472 KB Output is correct
17 Correct 847 ms 56488 KB Output is correct
18 Correct 965 ms 64724 KB Output is correct
19 Correct 996 ms 73848 KB Output is correct
20 Correct 1155 ms 80472 KB Output is correct
21 Correct 1051 ms 90704 KB Output is correct
22 Correct 1079 ms 97916 KB Output is correct
23 Correct 1098 ms 106484 KB Output is correct
24 Correct 988 ms 113412 KB Output is correct
25 Correct 933 ms 120588 KB Output is correct