Submission #1162694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162694		coolsentenceidontremember	Election (BOI18_election)	C++20	100 / 100	420 ms	30940 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);
  }
}

struct node {
  int sfx, sum;
  node() { sfx = sum = 0; }
};

struct query {
  int l, r, id;
  query(int lll, int rr, int idd) : l(lll), r(rr), id(idd) {}
  friend bool operator<(const query &dis, const query &other) {
    return dis.l > other.l;
  }
};

std::vector<node> st;

node comb(const node &l, const node &r) {
  node ret;
  ret.sum = l.sum + r.sum;
  ret.sfx = std::min(l.sfx + r.sum, r.sfx);
  return ret;
}

void upd(const int &id, const int &l, const int &r, const int &p,
         const int &v) {
  if (l == r) {
    st[id].sum = v;
    st[id].sfx = std::min(v, 0);
    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] = comb(st[id << 1], st[(id << 1) | 1]);
  return;
}

node get(const int &id, const int &l, const int &r, const int &u,
         const int &v) {
  // std::cout << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << '\n';
  if (l > v || r < u) {
    node ret;
    ret.sfx = ret.sum = 0;
    return ret;
  }
  if (l >= u && r <= v)
    return st[id];
  int m = (l + r) >> 1;
  return comb(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<node>((n << 2) + 5);
  std::string s;
  std::cin >> s;
  std::vector<int> vote;
  for (const char &c : s)
    vote.push_back(c == 'C' ? 1 : -1);
  for (int i = 0; i < n; i++)
    upd(1, 0, n - 1, i, 1);
  int q;
  std::cin >> q;
  std::vector<query> queries;
  for (int i = 0; i < q; i++) {
    int l, r;
    std::cin >> l >> r;
    query qq(--l, --r, i);
    queries.push_back(qq);
  }
  std::sort(queries.begin(), queries.end());
  int done = 0;
  std::vector<int> tony;
  std::vector<int> ans(q);
  for (int i = n - 1; i >= 0; i--) {
    if (vote[i] == -1) {
      tony.push_back(i);
      upd(1, 0, n - 1, i, 0);
    } else {
      if (!tony.empty()) {
        int sw = tony.back();
        upd(1, 0, n - 1, sw, -1);
        tony.pop_back();
      }
    }
    while (done < q && queries[done].l >= i) {
      const query &qq = queries[done];
      ans[qq.id] = (int)(std::upper_bound(tony.rbegin(), tony.rend(), qq.r) -
                         tony.rbegin()) -
                   get(1, 0, n - 1, 0, qq.r).sfx;
      // std::cout << get(1, 0, n - 1, 0, qq.r).sfx << std::endl;
      done++;
    }
  }
  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: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18