Submission #61457

#	Time	Username	Problem	Language	Result	Execution time	Memory
61457		khsoo01	Election (BOI18_election)	C++11	100 / 100	1662 ms	121640 KiB

election

#include<bits/stdc++.h>
using namespace std;

const int N = 500005, L = 524288, G = 19, inf = 1e9;

int n, q, a[N];
char ipt[N];

struct data {int i, m, x;} s[N][G];

struct segtree {
	int v[2*L];
	void build () {
		for(int i=1;i<=n;i++) {
			v[L+i] = a[i];
		}
		for(int i=L;--i;) {
			v[i] = max(v[2*i], v[2*i+1]);
		}
	}
	int get (int S, int E) {
		int R = -inf;
		S += L;
		E += L;
		while(S <= E) {
			if(S%2 == 1) R = max(R, v[S++]);
			if(E%2 == 0) R = max(R, v[E--]);
			S /= 2;
			E /= 2;
		}
		return R;
	}
} seg;

int main()
{
	scanf("%d%s",&n,ipt+1);
	for(int i=1;i<=n;i++) {
		a[i] = a[i-1] + (1 - 2 * (ipt[i] == 'T'));
	}
	seg.build();
	s[n+1][0] = {n+1, 0, 0};
	for(int i=n+1;i>=1;i--) {
		if(ipt[i] == 'T') {
			s[i][0] = {i+1, 0, 1};
		}
		if(ipt[i] == 'C') {
			int I = i+1, M = 0;
			for(int j=G;j--;) {
				if(s[I][j].x) continue;
				M = max(M, s[I][j].m);
				I = s[I][j].i;
			}
			I = min(I, n);
			s[i][0] = {I+1, M+1, 0};
		}
		for(int j=1;j<G;j++) {
			int I = s[i][j-1].i;
			s[i][j] = {s[I][j-1].i, max(s[i][j-1].m, s[I][j-1].m), s[i][j-1].x + s[I][j-1].x};
		}
	}
	scanf("%d",&q);
	while(q--) {
		int A, B, M = 0, R = 0;
		scanf("%d%d",&A,&B);
		for(int i=G;i--;) {
			if(s[A][i].i > B) continue;
			M = max(M, s[A][i].m);
			R += s[A][i].x;
			A = s[A][i].i;
		}
		M = max(M, seg.get(A, B) - a[A-1]);
		printf("%d\n",R+M-(a[B]-a[A-1]));
	}
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s",&n,ipt+1);
  ~~~~~^~~~~~~~~~~~~~~~~
election.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
election.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

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