Submission #108545

#	Time	Username	Problem	Language	Result	Execution time	Memory
108545		DystoriaX	Election (BOI18_election)	C++14	0 / 100	4 ms	384 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct Node{
	int pref, suf;
};

int n, q;
int pref[500010], suf[500010];
char s[500010];
const int INF = 1e9;
Node st[4*500010];

void update(int l, int r, int pt, int i){
	if(r < pt || pt < l) return;

	if(l == r && l == pt){
		st[i].pref = pref[l];
		st[i].suf = suf[l];
		return;
	}

	int m = (l + r) >> 1;
	update(l, m, pt, i << 1);
	update(m + 1, r, pt, 1 + (i << 1));

	st[i].pref = min(st[i << 1].pref, st[1 + (i << 1)].pref);
	st[i].suf = min(st[i << 1].suf, st[1 + (i << 1)].suf);
}

Node query(int l, int r, int ls, int rs, int i){
	if(r < ls || rs < l) return Node({INF, INF});

	if(ls <= l && r <= rs) return st[i];

	int m = (l + r) >> 1;

	Node lf, rg;
	lf = query(l, m, ls, rs, i << 1);
	rg = query(m + 1, r, ls, rs, 1 + (i << 1));

	return Node({min(lf.pref, rg.pref), min(lf.suf, rg.suf)});
}

int main(){
	scanf("%d", &n);

	int bal = 0;
	for(int i = 1; i <= n; i++){
		scanf(" %c", &s[i]);
		if(s[i] == 'C') bal++;
		else bal--;
		pref[i] = bal;
	}

	bal = 0;
	for(int i = n; i >= 1; i--){
		if(s[i] == 'C') bal++;
		else bal--;
		suf[i] = bal;

		update(1, n, i, 1);
	}

	scanf("%d", &q);
	while(q--){
		int l, r;
		scanf("%d%d", &l, &r);
		Node x = query(1, n, l, r, 1);

		printf("%d\n", abs(min(x.pref - pref[l - 1], x.suf - suf[r + 1])));
	}


	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
election.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &s[i]);
   ~~~~~^~~~~~~~~~~~~~
election.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
election.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~

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