oj.uz

Submission #770491

# Submission time Handle Problem Language Result Execution time Memory
770491 2023-07-01T10:41:57 Z allllekssssa Election (BOI18_election) C++14
0 / 100
 1 ms 340 KB 
#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

const int inf = 1e9;
const int sz = 20;
const int maxN = 1<<sz;

struct node {
	int lef;
	int rig;
	int sum;
};

int n, q;
string s;
int dl[maxN], dr[maxN];

node merge(node nd1, node nd2) {
	return {max(nd1.lef, nd2.lef), max(nd1.rig, nd2.rig), max(nd1.sum, nd2.sum)};
}

node tree[maxN];

void update(node nd, int idx) {
   while(idx) {
   	 tree[idx] = merge(tree[idx], nd);
   	 idx/=2;
   }
}

node get(int idx, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) {
		return {-inf, -inf, -inf};
	}

	if (tl >= l && tr <= r) {
		return tree[idx];
	}

	int mid = (tl + tr) / 2;
	node nd1 = get(2 * idx, tl, mid, l, r);
	node nd2 = get(2 * idx + 1, mid + 1, tr, l, r);

	return merge(nd1, nd2);
}


int main() {

	cin >> n;
	cin >> s;
	cin >> q;

	for (int i = 1; i < sz; i++) {
		tree[i] = {-inf, -inf, -inf};
	}

	int cur = 0;
	for (int i = 1; i<=n; i++) {
		if (s[i - 1] == 'T') ++cur; else --cur;
		dl[i] = cur;
	}

	cur = 0;
	for (int i = n; i>0; i--) {
		dr[i] = cur;
		node nd = {dl[i], dr[i], dl[i] + dr[i]};
		update(nd, i + sz/2 - 1);
		if (s[i - 1] == 'T') ++cur; else --cur;
	}

	while(q--) {
		int l, r;
		scanf("%d%d", &l, &r);
		node nd = get(1, 1, sz/2, l, r);
		int pl = dl[l - 1];
		int pr = dr[r];
	    int ans = max(0, max(nd.lef - pl, max(nd.rig - pr, nd.sum - pl - pr)));
	    printf("%d\n", ans);
	}
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -