oj.uz

Submission #447582

# Submission time Handle Problem Language Result Execution time Memory
447582 2021-07-26T21:19:00 Z socho Election (BOI18_election) C++14
100 / 100
 1345 ms 29948 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 181 ms 6120 KB Output is correct
7 Correct 157 ms 5956 KB Output is correct
8 Correct 163 ms 5984 KB Output is correct
9 Correct 160 ms 6024 KB Output is correct
10 Correct 160 ms 5904 KB Output is correct
11 Correct 160 ms 6212 KB Output is correct
12 Correct 159 ms 6084 KB Output is correct
13 Correct 166 ms 6072 KB Output is correct
14 Correct 163 ms 6088 KB Output is correct
15 Correct 172 ms 6040 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 432 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 181 ms 6120 KB Output is correct
7 Correct 157 ms 5956 KB Output is correct
8 Correct 163 ms 5984 KB Output is correct
9 Correct 160 ms 6024 KB Output is correct
10 Correct 160 ms 5904 KB Output is correct
11 Correct 160 ms 6212 KB Output is correct
12 Correct 159 ms 6084 KB Output is correct
13 Correct 166 ms 6072 KB Output is correct
14 Correct 163 ms 6088 KB Output is correct
15 Correct 172 ms 6040 KB Output is correct
16 Correct 1285 ms 29092 KB Output is correct
17 Correct 1226 ms 28556 KB Output is correct
18 Correct 1228 ms 28808 KB Output is correct
19 Correct 1191 ms 28336 KB Output is correct
20 Correct 1287 ms 28024 KB Output is correct
21 Correct 1257 ms 29768 KB Output is correct
22 Correct 1297 ms 29728 KB Output is correct
23 Correct 1287 ms 29948 KB Output is correct
24 Correct 1345 ms 29512 KB Output is correct
25 Correct 1291 ms 29112 KB Output is correct