Submission #806999

#	Time	Username	Problem	Language	Result	Execution time	Memory
806999		MODDI	Election (BOI18_election)	C++14	82 / 100	3065 ms	96488 KiB

election

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
int N, M, nxt[500009][2], nxtS[500009], 
nextC[500009], s[500009], a[500009], maxS[19][500009], minSuf[500009][19], lg[500009], lst[1000009];
char sir[500009];
void buildRMQ ()
{
    for (int i=1; i<=N; i++)
        maxS[0][i] = s[i];
    for (int i=2; i<=N; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i=1; i<=lg[N]; i++)
        for (int j=1; j + (1 << i) - 1 <= N; j++)
            maxS[i][j] = max (maxS[i - 1][j], maxS[i - 1][j + (1 << (i - 1))]);
}
int getMinSuf (int i, int j)
{
    int p = lg[j - i + 1];
    ///s[j] - max (s[i - 1 <= p <= j])
    int curr = max (max (maxS[p][i], maxS[p][j - (1 << p) + 1]), s[i - 1]);
    return s[j] - curr;
}
 
int getS (int i, int j)
{
    return s[j] - s[i - 1];
}
 
int main ()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	cin>>sir+1;
	for (int i=1; i<=N; i++)
	    a[i] = (sir[i] == 'C' ? +1 : -1),
	    s[i] = s[i - 1] + a[i];
	buildRMQ ();
	for (int i=N; i>=1; i--)
	    if (sir[i] == 'C') nextC[i] = i;
	    else nextC[i] = nextC[i + 1];
	for (int i=N; i>=0; i--)
	    nxtS[i] = lst[s[i] + N],
	    lst[s[i] + N] = i;
	for (int i=1; i<=N; i++)
	    if (nxtS[i - 1] == 0) nxt[i][0] = N + 1;
	    else
	    nxt[i][0] = nextC[nxtS[i - 1] + 1],
	    minSuf[i][0] = getMinSuf (i, nxtS[i - 1]);
	for (int i=1; i<=N; i++)
	    if (nxt[i][0] == 0)
	        nxt[i][0] = N + 1;
	cin>>M;
	while (M --)
	{
	    int L, R;
	    cin>>L>>R;
	    if (nextC[L] == 0 || nextC[L] > R)
	    {
	    	cout<<R-L+1<<"\n";
	        continue;
	    }
	    int mini = 0, ans = 0, cnt = nextC[L] - L, pos = nextC[L];
	    while (1)
	    {
	        if (nxt[pos][0] <= R)
	        {
	            cnt += nxt[pos][0] - (nxtS[pos - 1] + 1);
	            mini = min (mini, minSuf[pos][0]), pos = nxt[pos][0];
	            continue;
	        }
	        if (nxtS[pos - 1] == 0 || nxtS[pos - 1] >= R)
	            ans = cnt - min (getMinSuf (pos, R), mini + getS (pos, R));
	        else
	            ans = R - nxtS[pos - 1] + cnt - min (mini, minSuf[pos][0]);
	        break;
	    }
	    cout<<ans<<"\n";
	} 
	return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:41:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  cin>>sir+1;
      |       ~~~^~

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