Submission #171754

#	Time	Username	Problem	Language	Result	Execution time	Memory
171754		dndhk	Election (BOI18_election)	C++14	100 / 100	1700 ms	150232 KiB

election

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500010;
const int MAX_K = 20;

int N, Q;
string str;
int d[MAX_N+1];

struct S{
	int idx, mx, cnt;
};
S nxt[MAX_N+1][MAX_K+1];

struct SEG{
	struct NODE{
		int l, r;
		int mx;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, -INF});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 0, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	{
			seg[idx].mx = d[s];
			return;
		}
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
	}
	int Mx(int x, int y){
		return mx(0, 0, SZ, x, y);
	}
	int mx(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y){
			return seg[idx].mx;
		}
		if(x>e || y<s)	return -INF;
		return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
	}
}Seg;

vector<int> st;

int main(){
	scanf("%d", &N);
	cin>>str;
	str.pb('0');
	for(int i=str.size(); i>0; i--){
		str[i] = str[i-1];
	}
	for(int i=1; i<=N; i++){
		d[i] = d[i-1];
		if(str[i]=='C')	d[i]++;
		else	d[i]--;
	}
	for(int i=0; i<MAX_K; i++)	nxt[N+1][i].idx = N+1;
	Seg.Init(N);
	for(int i=N; i>=0; i--){
		while(!st.empty() && d[st.back()]>d[i])	st.pop_back();
		if(st.empty()){
			nxt[i][0].idx = N+1;
			nxt[i][0].mx = nxt[i][0].cnt = 0;
		}else{
			if(d[st.back()]==d[i]){
				nxt[i][0].idx = st.back();
				nxt[i][0].mx = Seg.Mx(i, st.back()) - d[i];
				nxt[i][0].cnt = 0;
				st.pop_back();
			}else{
				nxt[i][0].idx = st.back();
				nxt[i][0].mx = 0;
				nxt[i][0].cnt = 1;
			}
		}
		for(int j=1; j<MAX_K; j++){
			nxt[i][j].idx = nxt[nxt[i][j-1].idx][j-1].idx;
			nxt[i][j].mx = max(nxt[i][j-1].mx, nxt[nxt[i][j-1].idx][j-1].mx);
			nxt[i][j].cnt = nxt[i][j-1].cnt + nxt[nxt[i][j-1].idx][j-1].cnt;
		}
		st.push_back(i);
	}
	scanf("%d", &Q);
	int t, dh, ans;
	while(Q--){
		int a, b; scanf("%d%d", &a, &b); a--;
		t = a, dh = 0, ans = 0;
		for(int i=MAX_K-1; i>=0; i--){
			if(nxt[t][i].idx<=b){
				ans+=nxt[t][i].cnt;
				dh = max(dh, nxt[t][i].mx);
				t = nxt[t][i].idx;
			}
		}
		dh = max(dh, Seg.Mx(t, b) - d[t]);
		dh -= (d[b] - d[t]);
		ans += max(0, dh);
		printf("%d\n", ans);
	}

	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
election.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
election.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b); a--;
             ~~~~~^~~~~~~~~~~~~~~~

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