Submission #73847

#TimeUsernameProblemLanguageResultExecution timeMemory
73847jiaqing23Election (BOI18_election)C++14
28 / 100
3032 ms1300 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> pi; typedef vector<ll> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; typedef pair<int,pair<int,int> > tri; int n, q; string s; int used[500050]; void calcpre(int l, int r){ int now = 0; for(int i = l; i <= r; i++){ if(used[i]) continue; if(s[i] == 'C') now--; else now++; if(now > 0){ used[i] = 1; now--; } } } void calcsuf(int l, int r){ int now = 0; for(int i = r; i >= l; i--){ if(used[i]) continue; if(s[i] == 'C') now--; else now++; if(now > 0){ used[i] = 1; now--; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> s >> q; while(q--){ int l, r; cin >> l >> r; l--; r--; calcpre(l,r); calcsuf(l,r); int ans = 0; for(int i = l; i <= r; i++) { if(used[i]) ans++; used[i] = 0; } cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...