Submission #68366

#	Time	Username	Problem	Language	Result	Execution time	Memory
68366		Bruteforceman	Election (BOI18_election)	C++11	100 / 100	1316 ms	138108 KiB

election

#include "bits/stdc++.h"
using namespace std;
int a[500010];
int p[500010];

int solve(int l, int r) {
	int cur = 0;
	int ans = 0;
	int mx = 0;
	int mn = 0;
	for(int i = l; i <= r; i++) {
		cur += a[i];
		mn = min(mn, cur);
		mx = max(mx, cur - mn);
	}
	ans += mx - cur;
	cout << mx << ' ' << cur << endl;
	return ans;
}
char s[500010];
int opt[500010];
const int inf = 1e9;
vector <pair <int, int>> g[500010];
int ans[500010];
int n;

int t[500010 * 4];
int prop[500010 * 4];
int rmq[500010 * 4];

void pushdown(int c) {
	int l = c << 1;
	int r = l + 1;
	t[l] = max(t[l], rmq[l] - prop[c]);
	t[r] = max(t[r], rmq[r] - prop[c]);
	prop[l] = min(prop[l], prop[c]);
	prop[r] = min(prop[r], prop[c]);
}
void update(int x, int y, int val, int c = 1, int b = 1, int e = n) {
	if(x <= b && e <= y) {
		prop[c] = min(prop[c], val);
		t[c] = max(t[c], rmq[c] - prop[c]);
		return ;
	}
	if(y < b || e < x) return ;
	pushdown(c);
	int l = c << 1;
	int r = l + 1;
	int m = (b + e) >> 1;
	update(x, y, val, l, b, m);
	update(x, y, val, r, m+1, e);
	t[c] = max(t[l], t[r]);
}
int query(int x, int y, int c = 1, int b = 1, int e = n) {
	if(x <= b && e <= y) {
		return t[c];
	}
	if(y < b || e < x) return -inf;
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	return max(query(x, y, l, b, m), query(x, y, r, m+1, e));
} 
void build(int c = 1, int b = 1, int e = n) {
	if(b == e) {
		rmq[c] = p[b];
		return ;
	} 
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	build(l, b, m);
	build(r, m+1, e);
	rmq[c] = max(rmq[l], rmq[r]);
}

int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	scanf("%s", s);
	for(int i = 1; i <= n; i++) {
		a[i] = s[i - 1] == 'C' ? 1 : -1;
	}
	int q;
	scanf("%d", &q);
	int id = 0;
	while(q--) {
		int l, r;
		scanf("%d %d", &l, &r);
		g[l].emplace_back(r, id++);
	}
	fill(opt, opt + n + 1, inf);
	fill(prop, prop + (4 * n) + 1, inf);
	fill(t, t + (4 * n) + 1, -inf);

	int add = 0;
	for(int i = n; i >= 1; i--) {
		p[i] = -add;
		add += a[i];
	}
	build();

	add = 0;
	for(int i = n; i >= 1; i--) {
		add += a[i];
		update(i, n, min(p[i], -add));
		for(auto j : g[i]) {
			int mx = query(i, j.first);
			ans[j.second] = mx - (p[j.first] + add);
		}
	}
	for(int i = 0; i < id; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main(int, const char**)':
election.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
election.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
  ~~~~~^~~~~~~~~
election.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
election.cpp:90: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: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18