Submission #287799

#	Time	Username	Problem	Language	Result	Execution time	Memory
287799		VROOM_VARUN	Election (BOI18_election)	C++14	0 / 100	3 ms	640 KiB

election

/*
ID: varunra2
LANG: C++
TASK: elections
*/

#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<ll> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

struct node{
  ll pref = 0;
  ll suf = 0;
  ll tot = 0;
  ll ret = 0;
};

node comb(node a, node b) {
  node ret;
  ret.pref = max(0ll, max(a.pref, a.tot + b.pref));
  ret.suf = max(0ll, max(b.suf, b.tot + a.suf));
  ret.tot = a.tot + b.tot;
  ret.ret = max(max(a.ret + b.tot, a.tot + b.ret), a.pref + b.suf);
  return ret;
}

vector<node> segtree;
VI l;
VI r;
string s;
VI vals;
int n;
int q;
node bad;

void init() {
  l.resize(q);
  r.resize(q);
  segtree.resize(4 * n);
  vals.resize(n);
}

void build(int l = 0, int r = n - 1, int node = 0) {
  if(l == r) {
    segtree[node].pref = max(0ll, vals[l]);
    segtree[node].suf = max(0ll, vals[l]);
    segtree[node].tot = vals[l];
    segtree[node].ret = (vals[l] == 1 ? 1 : 0);
    return;
  }

  int mid = (l + r)/2;

  build(l, mid, 2 * node + 1);
  build(mid + 1, r, 2 * node + 2);

  segtree[node] = comb(segtree[2 * node + 1], segtree[2 * node + 2]);
}

node qry(int tl, int tr, int l, int r, int node) {
  if(tl > tr) return bad;
  if(tl > r or tr < l) return bad;
  if(tl >= l and tr <= r) {
    return segtree[node];
  }
  int mid = (tl + tr)/2;;
  return comb(qry(tl, mid, l, r, 2 * node + 1), qry(mid + 1, tr, l, r, 2 * node + 2));
}

int qry(int l, int r) {
  node ret = qry(0, n - 1, l, r, 0);
  return ret.ret;
}


int main() {
#ifndef ONLINE_JUDGE
  freopen("elections.in", "r", stdin);
  freopen("elections.out", "w", stdout);
#endif
  cin.sync_with_stdio(0); cin.tie(0);
  cin >> n;
  cin >> s;
  cin >> q;

  init();

  for(int i = 0; i < q; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
  }

  for(int i = 0; i < n; i++) {
    vals[i] = (s[i] == 'C' ? -1 : 1);
  }

  build();

  for(int i = 0; i < q; i++) {
    cout << qry(l[i], r[i]) << '\n';
  }


  return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:122:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  122 |   freopen("elections.in", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:123:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   freopen("elections.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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