제출 #1217407

#제출 시각아이디문제언어결과실행 시간메모리
1217407stevend57Election (BOI18_election)C++20
0 / 100
2 ms320 KiB
#include <iostream> #include <vector> using namespace std; struct Vote { int c = 0, tl = 0, tr = 0, tsum = 0; Vote() = default; Vote(char ch) { c = tl = tr = tsum = 0; if (ch == 'C') { c = 1; } else if (ch == 'T') { tsum = tl = tr = 1; } } Vote operator+(const Vote& other) const { Vote res; int tt = tr + other.tl; int cc = min(c, other.c); int match = min(tt, cc); res.tsum = tsum + other.tsum - match; res.c = c + other.c - 2 * match; if (res.c == 0) { res.tl = res.tr = (c > 0 ? tl : 0) + tt + (other.c > 0 ? other.tr : 0) - match; } else { res.tl = (c > 0 ? tl : 0) + (c < other.c ? tt - match : 0); res.tr = (c > other.c ? tt - match : 0) + (other.c > 0 ? other.tr : 0); } // cout << "c: " << c << ", other.c: " << other.c << endl; // cout << "tl: " << tl << ", other.tl: " << other.tl << endl; // cout << "tr: " << tr << ", other.tr: " << other.tr << endl; // cout << "tsum: " << tsum << ", other.tsum: " << other.tsum << endl; // cout << "tt: " << tt << ", match: " << match << endl; // cout << "res.c: " << res.c << ", res.tl: " << res.tl << ", res.tr: " << res.tr << ", res.tsum: " << res.tsum << endl; return res; } }; struct St { int n; vector<Vote> t; St(int n) : n(n), t(n << 1) {} void build(const string& s) { for (size_t i = 0; i < s.size(); ++i) { t[n + i] = Vote(s[i]); } for (int i = n - 1; i > 0; --i) { t[i] = t[i << 1] + t[i << 1 | 1]; } } Vote query(int l, int r) { Vote resl, resr; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) resl = resl + t[l++]; if (r & 1) resr = t[--r] + resr; } return resl + resr; } }; int main() { int n; cin >> n; string s; cin >> s; St st(n); st.build(s); int q; cin >> q; while (q--) { int l, r; cin >> l >> r; Vote res = st.query(l - 1, r); cout << res.tsum << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...