Submission #72707

#TimeUsernameProblemLanguageResultExecution timeMemory
72707evpipisElection (BOI18_election)C++14
100 / 100
1408 ms127060 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef long long ll; typedef pair<int, int> ii; const int len = 5e5+5, inf = 1e9; int out[len], tree[4*len], lazy[4*len], pref[len], arr[len]; ii ask[len]; char str[len]; vector<int> st, vec[len]; void build(int p, int l, int r){ if (l == r) tree[p] = pref[l], lazy[p] = 0; else{ int mid = (l+r)/2; build(2*p, l, mid); build(2*p+1, mid+1, r); tree[p] = min(tree[2*p], tree[2*p+1]); lazy[p] = 0; } } void prop(int p, int l, int r){ if (lazy[p] == 0) return; tree[p] += lazy[p]; if (l != r){ lazy[2*p] += lazy[p]; lazy[2*p+1] += lazy[p]; } lazy[p] = 0; } void update(int p, int l, int r, int i, int j, int v){ prop(p, l, r); if (i <= l && r <= j) lazy[p] += v; else if (r < i || j < l) return; else{ int mid = (l+r)/2; update(2*p, l, mid, i, j, v); update(2*p+1, mid+1, r, i, j, v); prop(2*p, l, mid); prop(2*p+1, mid+1, r); tree[p] = min(tree[2*p], tree[2*p+1]); } } int query(int p, int l, int r, int i, int j){ prop(p, l, r); if (i <= l && r <= j) return tree[p]; if (r < i || j < l) return inf; int mid = (l+r)/2; return min(query(2*p, l, mid, i, j), query(2*p+1, mid+1, r, i, j)); } int bs(int x){ int l = 0, r = (int)st.size()-1, ans = (int)st.size(); while (l <= r){ int mid = (l+r)/2; if (st[mid] >= x) ans = mid, r = mid-1; else l = mid+1; } return ans; } int main(){ int n, q; scanf("%d %s", &n, &str); for (int i = 1; i <= n; i++){ if (str[i-1] == 'C') arr[i] = 1; else arr[i] = -1; pref[i] = pref[i-1] + arr[i]; } build(1, 1, n); scanf("%d", &q); for (int i = 0; i < q; i++){ scanf("%d %d", &ask[i].fi, &ask[i].se); vec[ask[i].se].pb(i); } for (int i = 1; i <= n; i++){ if (arr[i] == 1 && !st.empty()){ update(1, 1, n, st.back(), n, -1); st.pop_back(); } if (arr[i] == -1){ update(1, 1, n, i, n, +1); st.pb(i); } for (int j = 0; j < vec[i].size(); j++){ int l = ask[vec[i][j]].fi, r = i, lef = bs(l), rig = st.size()-lef; //if (i == 17){ // printf("l = %d, r = %d, lef = %d, rig = %d\n", l, r, lef, rig); //printf("mn = %d\n", query(1, 1, n, l, r) - pref[l-1] - lef); //} out[vec[i][j]] = rig - min(0, query(1, 1, n, l, r)-pref[l-1]-lef); } } for (int i = 0; i < q; i++) printf("%d\n", out[i]); return 0; } /* 17 TTCTTCCCTCTTTTCTC 1 14 17 */

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:82:28: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[500005]' [-Wformat=]
     scanf("%d %s", &n, &str);
                        ~~~~^
election.cpp:108:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec[i].size(); j++){
                         ~~^~~~~~~~~~~~~~~
election.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %s", &n, &str);
     ~~~~~^~~~~~~~~~~~~~~~~~~
election.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
election.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &ask[i].fi, &ask[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...