oj.uz

Submission #108545

# Submission time Handle Problem Language Result Execution time Memory
108545 2019-04-30T07:26:59 Z DystoriaX Election (BOI18_election) C++14
0 / 100
 4 ms 384 KB 
#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

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

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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