Submission #447582

#	Time	Username	Problem	Language	Result	Execution time	Memory
447582		socho	Election (BOI18_election)	C++14	100 / 100	1345 ms	29948 KiB

election

#include <bits/stdc++.h>
using namespace std;
void fast() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
	srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
	long long a = rand();
	long long b = rand();
	return a * (RAND_MAX + 1ll) + b;
}
void usaco() {
	freopen("problem.in", "r", stdin); 
	freopen("problem.out", "w", stdout);
}
template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
// #define endl '\n'
// #define double long double
// #define int long long
// const int MOD = 1000 * 1000 * 1000 + 7;
// const int MOD = 998244353;

const int MXN = 500005;
int a[MXN];
int n;
string s;

struct info {
	
	int mxpf, mxsf, sm, ans;
	
} seg[MXN * 4];

info get(int x) {
	info res;
	if (x == 1) {
		res.mxpf = res.mxsf = res.sm = res.ans = 1;
	}
	else if (x == -1) {
		res.mxpf = res.mxsf = 0;
		res.sm = -1;
		res.ans = 0;
	}
	return res;
}

info comb(info a, info b) {
	info res;
	res.mxpf = max(a.mxpf, a.sm + b.mxpf);
	res.mxsf = max(b.mxsf, b.sm + a.mxsf);
	res.sm = a.sm + b.sm;
	res.ans = max(max(a.ans + b.sm, a.sm + b.ans), a.mxpf + b.mxsf);
	return res;
}

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = get(a[l]);
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = comb(seg[ind*2], seg[ind*2+1]);
}

vector<info> sto;
void solve(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		sto.push_back(seg[ind]);
		return;
	}
	if (ql > r || qr < l) return;
	int m = (l + r) / 2;
	solve(ind*2, l, m, ql, qr);
	solve(ind*2+1, m+1, r, ql, qr);
}

signed main() {

	ran(); fast();

	cin >> n;
	cin >> s;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'T') a[i] = 1;
		else a[i] = -1;
	}
	
	build(1, 0, n-1);
	
	int w;
	cin >> w;
	while (w--) {
		int l, r;
		cin >> l >> r;
		l--; r--;
		sto.clear();
		solve(1, 0, n-1, l, r);
		info cr = sto[0];
		for (int i=1; i<sto.size(); i++) cr = comb(cr, sto[i]);
		cout << cr.ans << endl;
	}

}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for (int i=1; i<sto.size(); i++) cr = comb(cr, sto[i]);
      |                 ~^~~~~~~~~~~
election.cpp: In function 'void usaco()':
election.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen("problem.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:16:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  freopen("problem.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18