oj.uz

Submission #806999

# Submission time Handle Problem Language Result Execution time Memory
806999 2023-08-04T12:10:55 Z MODDI Election (BOI18_election) C++14
82 / 100
 3000 ms 96488 KB 
#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

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

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 76 ms 12540 KB Output is correct
7 Correct 73 ms 12904 KB Output is correct
8 Correct 31 ms 12968 KB Output is correct
9 Correct 33 ms 12928 KB Output is correct
10 Correct 26 ms 12964 KB Output is correct
11 Correct 604 ms 13164 KB Output is correct
12 Correct 23 ms 12604 KB Output is correct
13 Correct 22 ms 11340 KB Output is correct
14 Correct 21 ms 12184 KB Output is correct
15 Correct 22 ms 11076 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 76 ms 12540 KB Output is correct
7 Correct 73 ms 12904 KB Output is correct
8 Correct 31 ms 12968 KB Output is correct
9 Correct 33 ms 12928 KB Output is correct
10 Correct 26 ms 12964 KB Output is correct
11 Correct 604 ms 13164 KB Output is correct
12 Correct 23 ms 12604 KB Output is correct
13 Correct 22 ms 11340 KB Output is correct
14 Correct 21 ms 12184 KB Output is correct
15 Correct 22 ms 11076 KB Output is correct
16 Correct 1032 ms 96488 KB Output is correct
17 Correct 251 ms 96024 KB Output is correct
18 Correct 688 ms 96408 KB Output is correct
19 Correct 806 ms 95816 KB Output is correct
20 Correct 315 ms 95968 KB Output is correct
21 Execution timed out 3065 ms 88516 KB Time limit exceeded
22 Halted 0 ms 0 KB -