Submission #1264646

#TimeUsernameProblemLanguageResultExecution timeMemory
1264646yoshi_33550336Election (BOI18_election)C++20
0 / 100
10 ms15936 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #ifndef yoshi_likes_e4 #define endl '\n' #endif #define problem "election" #define multitest 0 #define debug(x) cerr << #x << " = " << x << endl; void init() { } struct Node { int RS; int Sum = 0; Node() { RS = 1e9; } Node(int x) { RS = Sum = x; } }; Node merge(const Node &L, const Node &R) { if (L.RS == 1e9) return R; if (R.RS == 1e9) return L; Node res; res.RS = min(R.RS, R.Sum + L.RS); res.Sum = L.Sum + R.Sum; return res; } struct ST { vector<Node> t; int n = 0; ST() { } ST(int n) : n(n) { t.resize(2 * n); fill(t.begin() + n, t.end(), Node(0)); for (int i = n - 1; i > 0; i--) t[i] = merge(t[2 * i], t[2 * i + 1]); } void modify(int p, int value) { for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = merge(t[p - (p & 1)], t[p + (~p & 1)]); } Node query(int l, int r) { Node resl, resr; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, t[l++]); if (r & 1) resr = merge(t[--r], resr); } return merge(resl, resr); } }; ST Stx(500000); struct Tp3 { int x, y, z; }; void Yoshi() { int n; cin >> n; string s; cin >> s; int q; cin >> q; vector<Tp3> qus(q); for (auto &i : qus) cin >> i.x >> i.y, i.x--, i.y--, i.z = &i - &qus[0]; sort(qus.begin(), qus.end(), [](auto &a, auto &b) { return a.x > b.x; }); vector<int> Tp, qres(q); int ptr = n - 1; for (auto &[l, r, id] : qus) { while (ptr >= l) { if (s[ptr] == 'T') Tp.push_back(ptr); else { Stx.modify(ptr, 1); if (Tp.size()) { Stx.modify(Tp.back(), -1); Tp.pop_back(); } } ptr--; } qres[id] = upper_bound(Tp.rbegin(), Tp.rend(), r) - Tp.rbegin() - Stx.query(l, r + 1).RS; } for (auto &i : qres) cout << i << endl; } signed main() { #ifndef yoshi_likes_e4 ios::sync_with_stdio(0); cin.tie(0); if (fopen(problem ".inp", "r")) { freopen(problem ".inp", "r", stdin); freopen(problem ".out", "w", stdout); } #endif init(); int t = 1; #if multitest cin >> t; #endif while (t--) Yoshi(); }

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...