| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171754 |
2019-12-30T09:55:48 Z |
dndhk |
Election (BOI18_election) |
C++14 |
|
1700 ms |
150232 KB |
#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
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--;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
5 ms |
888 KB |
Output is correct |
| 5 |
Correct |
5 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
5 ms |
888 KB |
Output is correct |
| 5 |
Correct |
5 ms |
888 KB |
Output is correct |
| 6 |
Correct |
142 ms |
20564 KB |
Output is correct |
| 7 |
Correct |
110 ms |
20492 KB |
Output is correct |
| 8 |
Correct |
121 ms |
20384 KB |
Output is correct |
| 9 |
Correct |
118 ms |
20396 KB |
Output is correct |
| 10 |
Correct |
131 ms |
20356 KB |
Output is correct |
| 11 |
Correct |
144 ms |
20520 KB |
Output is correct |
| 12 |
Correct |
132 ms |
20512 KB |
Output is correct |
| 13 |
Correct |
140 ms |
20660 KB |
Output is correct |
| 14 |
Correct |
128 ms |
20604 KB |
Output is correct |
| 15 |
Correct |
130 ms |
20516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
5 ms |
888 KB |
Output is correct |
| 5 |
Correct |
5 ms |
888 KB |
Output is correct |
| 6 |
Correct |
142 ms |
20564 KB |
Output is correct |
| 7 |
Correct |
110 ms |
20492 KB |
Output is correct |
| 8 |
Correct |
121 ms |
20384 KB |
Output is correct |
| 9 |
Correct |
118 ms |
20396 KB |
Output is correct |
| 10 |
Correct |
131 ms |
20356 KB |
Output is correct |
| 11 |
Correct |
144 ms |
20520 KB |
Output is correct |
| 12 |
Correct |
132 ms |
20512 KB |
Output is correct |
| 13 |
Correct |
140 ms |
20660 KB |
Output is correct |
| 14 |
Correct |
128 ms |
20604 KB |
Output is correct |
| 15 |
Correct |
130 ms |
20516 KB |
Output is correct |
| 16 |
Correct |
1072 ms |
140772 KB |
Output is correct |
| 17 |
Correct |
898 ms |
147848 KB |
Output is correct |
| 18 |
Correct |
944 ms |
148240 KB |
Output is correct |
| 19 |
Correct |
988 ms |
147584 KB |
Output is correct |
| 20 |
Correct |
1257 ms |
147472 KB |
Output is correct |
| 21 |
Correct |
1700 ms |
149284 KB |
Output is correct |
| 22 |
Correct |
1358 ms |
149200 KB |
Output is correct |
| 23 |
Correct |
1409 ms |
150232 KB |
Output is correct |
| 24 |
Correct |
1487 ms |
149004 KB |
Output is correct |
| 25 |
Correct |
1222 ms |
148520 KB |
Output is correct |
