Submission #1157291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157291		coolsentenceidontremember	Election (BOI18_election)	C++20	0 / 100	1 ms	320 KiB

election

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include "bits/stdc++.h"
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair

void setIO(std::string s = "") {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  if (!s.empty()) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
std::vector<int> vote;
std::vector<std::array<int, 3>> query;
std::vector<std::pair<int, int>> st;

std::pair<int, int> combine(const std::pair<int, int> l,
                            const std::pair<int, int> r) {
  return std::pair<int, int>(l.ff + r.ff, std::min(r.ss, l.ss + r.ff));
}

void upd(const int &id, const int &l, const int &r, const int &p,
         const int &v) {
  // std::cout << l << r << '\n';
  if (l == r) {
    st[id] = {v, v};
    return;
  }
  int m = (l + r) >> 1;
  if (p <= m)
    upd(id << 1, l, m, p, v);
  else
    upd(id << 1 | 1, m + 1, r, p, v);
  st[id] = combine(st[id << 1], st[id << 1 | 1]);
  return;
}

std::pair<int, int> get(const int &id, const int &l, const int &r, const int &u,
                        const int &v) {
  if (r < u || l > v)
    return std::pair<int, int>(0, 0);
  if (l >= u && r <= v)
    return st[id];
  int m = (l + r) >> 1;
  return combine(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
int main() {
  setIO();
  int n;
  std::cin >> n;
  st = std::vector<std::pair<int, int>>((n << 2) + 1, {0, 0});
  for (int i = 1; i <= n; i++) {
    char c;
    std::cin >> c;
    vote.push_back((c == 'C') ? 1 : -1);
  }
  int q;
  std::cin >> q;
  for (int i = 1; i < q; i++) {
    int l, r;
    std::cin >> l >> r;
    query.push_back({--l, --r, i});
  }
  std::sort(query.begin(), query.end(),
            [&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
              return a[0] > b[0];
            });
  std::vector<int> ans(q);
  int border = n - 1;
  std::vector<int> cur;
  for (const std::array<int, 3> &a : query) {
    int l = a[0], r = a[1], id = a[2];
    while (border >= l) {
      if (vote[border] == -1) {
        cur.push_back(border);
      } else {
        upd(1, 0, n - 1, border, 1);
        if (!cur.empty()) {
          int x = cur.back();
          upd(1, 0, n - 1, x, -1);
          cur.pop_back();
        }
      }
      border--;
    }
    ans[id] = std::upper_bound(cur.rbegin(), cur.rend(), r) - cur.rbegin() -
              get(1, 0, n - 1, l, r).ss;
  }
  for (int i = 0; i < q; i++) {
    std::cout << ans[i] << '\n';
  }
}

Compilation message (stderr)

election.cpp: In function 'void setIO(std::string)':
election.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18