Submission #89957

#	Time	Username	Problem	Language	Result	Execution time	Memory
89957		Good	Election (BOI18_election)	C++11	100 / 100	952 ms	121836 KiB

election

/*
ID: blackha5
TASK: test
LANG: C++
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ff first
#define ss second
#define Maxn 500003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

int n, q;
char a[Maxn];
int ans[Maxn];
int T[Maxn * 4][2];

vector <int> v, B;
vector <pii> A[Maxn];

void upd (int x, int y, int l, int r, int v) {
	if (l == r) {
		T[v][0] = y;
		T[v][1] = min (y, 0);
		return;
	}
	
	if (x <= mid (l, r))
		upd (x, y, l, mid (l, r), v * 2);
	else
		upd (x, y, mid (l, r) + 1, r, v * 2 + 1);
	
	T[v][0] = T[v * 2][0] + T[v * 2 + 1][0];
	T[v][1] = min (0, min (T[v * 2 + 1][1], T[v * 2][1] + T[v * 2 + 1][0]));		
}

void get (int x, int y, int l, int r, int v) {
	if (l >= x and r <= y) {
		B.pb (v);
		return;
	}	
	
	if (l > y or r < x)
		return;		
	
	get (x, y, l, mid (l, r), v * 2);
	get (x, y, mid (l, r) + 1, r, v * 2 + 1);		
}

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d %s %d", &n, &a, &q);

	int cnt = 0;
	while (cnt != q) {
		int l, r;
		scanf ("%d%d", &l, &r);
		
		A[l].pb ({r, ++cnt});
	}
	
	for (int i = n; i >= 1; i--) {
		if (a[i - 1] == 'C') {
			upd (i, 1, 1, n, 1);
			if (v.size() > 0) {
				upd (v.back(), -1, 1, n, 1);
				v.ppb();
			}
		}
		
		else
			v.pb (i);
			
		for (auto j: A[i]) {
			B.clear();
			get (i, j.ff, 1, n, 1);
			
			int x = 0, y = 0;
			for (int k = B.size() - 1; k >= 0; k--)
				x = min (x, y + T[B[k]][1]), y += T[B[k]][0];
			
			int l = 1;
			int r = v.size();
			
			int pos = 0;
			while (l <= r) {
				int md = mid (l, r);
				if (v[v.size() - md] <= j.ff)
					pos = md, l = md + 1;
				else
					r = md - 1;	
			}
			
			ans[j.ss] = max (-x, 0) + pos;
		}	
	}
	
	for (int i = 1; i <= q; i++)
		printf ("%d\n", ans[i]);
		
	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:69:31: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[500003]' [-Wformat=]
  scanf ("%d %s %d", &n, &a, &q);
                         ~~    ^
election.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %s %d", &n, &a, &q);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &l, &r);
   ~~~~~~^~~~~~~~~~~~~~~~

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