Submission #202867

#	Time	Username	Problem	Language	Result	Execution time	Memory
202867		quocnguyen1012	Election (BOI18_election)	C++14	0 / 100	24 ms	31608 KiB

election

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 5;

class node
{
public:
  int Min, sum;
  node(int Min = 0, int sum = 0):
    Min(Min), sum(sum) {}
  node operator + (const node & other) const
  {
    node res;
    res.Min = min(Min, sum + other.Min);
    res.sum = sum + other.sum;
    return res;
  }
};

pair<node, node> ST[4 * maxn];
int N; string str;

#define lc id << 1
#define rc id << 1 | 1

void build(int id, int l, int r)
{
  if (l == r){
    if (str[l] == 'C'){
      ST[id] = mp(node(0, 1), node(0, 1));
    }
    else{
      ST[id] = mp(node(-1, -1), node(-1, -1));
    }
    return;
  }
  int mid = (l + r) / 2;
  build(lc, l, mid); build(rc, mid + 1, r);
  ST[id].fi = ST[lc].fi + ST[rc].fi;
  ST[id].se = ST[rc].se + ST[lc].se;
}

pair<node, node> getsum(int id, int l, int r, int L, int R)
{
  if (l > R || L > r) return mp(node(0, 0), node(0, 0));
  if (L <= l && r <= R) return ST[id];
  int mid = (l + r) / 2;
  pair<node, node> lt = getsum(lc, l, mid, L, R);
  pair<node, node> rt = getsum(rc, mid + 1, r, L, R);
  return mp(lt.fi + rt.fi, rt.se + lt.se);
} 

#undef lc
#undef rc

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> str; str = " " + str;
  build(1, 1, N);
  int Q; cin >> Q;
  while (Q--){
    int l, r; cin >> l >> r;
    pair<node, node> res = getsum(1, 1, N, l, r);
    cout << -(min(res.fi.Min, res.se.Min)) << '\n';
  }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
election.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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