Submission #806999

#TimeUsernameProblemLanguageResultExecution timeMemory
806999MODDIElection (BOI18_election)C++14
82 / 100
3065 ms96488 KiB
#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;
      |       ~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...