Submission #202871

#	Time	Username	Problem	Language	Result	Execution time	Memory
202871		quocnguyen1012	Election (BOI18_election)	C++14	0 / 100	31 ms	47352 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, res;
  node(int Min = 0, int sum = 0, int res = 0):
    Min(Min), sum(sum), res(res) {}
  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

typedef pair<node, node> Node;

Node relax(Node x, Node y)
{
  Node ret;
  ret.fi = x.fi + y.fi;
  ret.se = y.se + x.se;
  ret.fi.res = max({x.fi.res, y.fi.res, -x.fi.Min - y.se.Min});
  ret.se.res = max({x.se.res, y.se.res, -x.fi.Min - y.se.Min});
  return ret;
}

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] = relax(ST[lc], ST[rc]);
}

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 relax(lt, rt);
}

#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 << res.fi.res << '\n';
  }
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:79: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:80: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