//----------vahagng----------// #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> using namespace std; // using namespace __gnu_pbds; // template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif void print(long long t) { cerr << t; } void print(int t) { cerr << t; } void print(string t) { cerr << t; } void print(char t) { cerr << t; } void print(double t) { cerr << t; } void print(long double t) { cerr << t; } void print(unsigned long long t) { cerr << t; } template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(T v[], V n) { cerr << "["; for (int i = 0; i < n; i++) { cerr << v[i] << " "; } cerr << "]"; } template <class T, class V> void print(pair <T, V> p) { cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}"; } template <class T> void print(vector <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; } template <class T> void print(set <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; } template <class T> void print(multiset <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; } template <class T, class V> void print(map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; } #define ll long long #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define ld long double #define sz(v) v.size() #define endl '\n' const ll inf = 2e18, mod = 1e9 + 7, mod2 = 998244353; void SetIO(string str = "") { if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } else { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } } void FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } const int N = 5e5 + 10, M = 1e7 + 10; mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) { res = (res * a) % mod; } b >>= 1; a = (a * a) % mod; } return res; } ll n, q, p[N], s[N], pt[N]; char c[N]; struct segtree{ struct Node{ ll lazy, sum, mx; }; int size = 1; vector<Node>stree; void init(){ while(size < n) size <<= 1; stree.assign(4*size, {0, 0}); } void push(int x, int lx, int rx){ if(rx - lx == 1){ return; } stree[2*x+1].lazy += stree[x].lazy; stree[2*x+2].lazy += stree[x].lazy; int m = (lx + rx)/2; stree[2*x+1].mx += stree[x].lazy; stree[2*x+2].mx += stree[x].lazy; stree[x].lazy = 0; } void upd(int l, int r, ll v, int x, int lx, int rx){ push(x, lx, rx); if(lx >= r || rx <= l) return ; if(lx >= l && rx <= r){ stree[x].lazy += v; stree[x].mx += v; return; } int m = (lx + rx)/2; upd(l, r, v, 2*x+1, lx, m); upd(l, r, v, 2*x+2, m, rx); stree[x].mx = min(stree[2*x+1].mx,stree[2*x+2].mx); } ll qry(int l, int r, int x, int lx, int rx){ push(x, lx, rx); if(lx >= r || rx <= l){ return inf; } if(lx >= l && rx <= r){ return stree[x].mx; } int m = (lx + rx)/2; ll ans_l = qry(l, r, 2*x+1, lx, m); ll ans_r = qry(l, r, 2*x+2, m, rx); return min(ans_l, ans_r); } void upd(int l, int r, ll val){ upd(l, r, val, 0, 0, size); } ll qry(int l, int r){ return qry(l, r, 0, 0, size); } } st1, st2; void solve(int tc) { cin >> n; st1.init(); st2.init(); for(int i = 1; i <= n; i++){ cin >> c[i]; pt[i] = pt[i-1]; if(c[i] == 'C') p[i] = p[i-1] + 1; else p[i] = p[i-1] - 1, pt[i]++; st1.upd(i, i + 1, p[i]); } for(int i = n; i >= 1; i--){ s[i] = s[i+1]; if(c[i] == 'C') s[i]++; else s[i]--; st2.upd(i, i + 1, s[i]); } cin >> q; while(q--){ int l, r; cin >> l >> r; int left = 0, right = pt[r] - pt[l-1], ans = -1; st1.upd(l, r + 1, -p[l-1]); st2.upd(l, r + 1, -s[r+1]); while(left <= right){ int mid = (left + right)/2; st1.upd(l, r+1, mid); st2.upd(l, r+1, mid); int r1 = st1.qry(l, r + 1); int r2 = st2.qry(l, r + 1); st1.upd(l, r+1, -mid); st2.upd(l, r+1, -mid); if(r1 >= 0 && r2 >= 0){ ans = mid; right = mid - 1; }else{ left = mid + 1; } } st1.upd(l, r + 1, p[l-1]); st2.upd(l, r + 1, s[r+1]); cout << ans << endl; } } void precalc() { } int main() { // SetIO("teamwork"); FastIO(); int test_case = 1; // cin >> test_case; precalc(); int cnt = 1; while (test_case--) { solve(cnt++); } return 0; }

election.cpp: In function 'void SetIO(std::string)':
election.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen((str + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen((str + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~