oj.uz

Submission #59945

# Submission time Handle Problem Language Result Execution time Memory
59945 2018-07-23T11:08:34 Z egorlifar Election (BOI18_election) C++17
100 / 100
 976 ms 39276 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 500228;



struct node
{
	int sum;
	int suff;
};


int n;
string s;
int val[MAXN];
int q;
vector<pair<int, int> > z[MAXN];
int ss = 1;
int ans[MAXN];
node d[MAXN * 4];


void calc(int v) {
	d[v].sum = d[v * 2].sum + d[v * 2 + 1].sum;
	d[v].suff = min(d[v * 2 + 1].suff, d[v * 2 + 1].sum + d[v * 2].suff);
}

void change(int i, int x) {
	d[i].sum = x;
	d[i].suff = min(x, 0);
	while (i >> 1 > 0) {
		i >>= 1;
		calc(i);
	}
}


node get(int v, int vl, int vr, int l, int r) {
	if (vl > r || vr < l) {
		node kek;
		kek.sum = 1e9;
		kek.suff = 1e9;
		return kek;
	}
	if (l <= vl && vr <= r) {
		return d[v];
	}
	node a = get(v * 2, vl, (vl + vr) / 2, l, r);
	node b = get(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r);
	if (b.sum > 1e6) {
		return a;
	}
	node c;
	c.suff = min(b.suff, a.suff + b.sum);
	c.sum = a.sum + b.sum;
	return c;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'T') {
			val[i] = -1;
		} else {
			val[i] = 1;
		}
	}
	cin >> q;
	for (int it = 0; it < q; it++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		z[l].pb({r, it});
	}
	while (ss < n) {
		ss <<= 1;
	}
	for (int i = 0; i < n; i++) {
		change(ss + i, 1);
	}
	//l[i] > lbal;
	//r[i] > rbal;
	vector<int> st;
	for (int i = n - 1; i >= 0; i--) {
		if (val[i] == -1) {
			st.pb(i);
			change(ss + i, 0);
		} else {
			if (!st.empty()) {
				change(ss + st.back(), -1);
				st.pop_back();
			}
		}
		for (auto q: z[i]) {
			ans[q.second] = upper_bound(rall(st), q.first) - st.rbegin() - get(1, 1, ss, 1, q.first + 1).suff;
		}
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0; 		
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12280 KB Output is correct
2 Correct 18 ms 12388 KB Output is correct
3 Correct 15 ms 12476 KB Output is correct
4 Correct 15 ms 12476 KB Output is correct
5 Correct 16 ms 12476 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12280 KB Output is correct
2 Correct 18 ms 12388 KB Output is correct
3 Correct 15 ms 12476 KB Output is correct
4 Correct 15 ms 12476 KB Output is correct
5 Correct 16 ms 12476 KB Output is correct
6 Correct 115 ms 15980 KB Output is correct
7 Correct 71 ms 15980 KB Output is correct
8 Correct 91 ms 15980 KB Output is correct
9 Correct 121 ms 15980 KB Output is correct
10 Correct 106 ms 15980 KB Output is correct
11 Correct 122 ms 16096 KB Output is correct
12 Correct 115 ms 16096 KB Output is correct
13 Correct 136 ms 16200 KB Output is correct
14 Correct 118 ms 16200 KB Output is correct
15 Correct 149 ms 16200 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12280 KB Output is correct
2 Correct 18 ms 12388 KB Output is correct
3 Correct 15 ms 12476 KB Output is correct
4 Correct 15 ms 12476 KB Output is correct
5 Correct 16 ms 12476 KB Output is correct
6 Correct 115 ms 15980 KB Output is correct
7 Correct 71 ms 15980 KB Output is correct
8 Correct 91 ms 15980 KB Output is correct
9 Correct 121 ms 15980 KB Output is correct
10 Correct 106 ms 15980 KB Output is correct
11 Correct 122 ms 16096 KB Output is correct
12 Correct 115 ms 16096 KB Output is correct
13 Correct 136 ms 16200 KB Output is correct
14 Correct 118 ms 16200 KB Output is correct
15 Correct 149 ms 16200 KB Output is correct
16 Correct 935 ms 37364 KB Output is correct
17 Correct 703 ms 37364 KB Output is correct
18 Correct 824 ms 37364 KB Output is correct
19 Correct 865 ms 37364 KB Output is correct
20 Correct 798 ms 37364 KB Output is correct
21 Correct 970 ms 38948 KB Output is correct
22 Correct 976 ms 38948 KB Output is correct
23 Correct 944 ms 39276 KB Output is correct
24 Correct 784 ms 39276 KB Output is correct
25 Correct 789 ms 39276 KB Output is correct