oj.uz

Submission #287804

# Submission time Handle Problem Language Result Execution time Memory
287804 2020-09-01T01:19:10 Z VROOM_VARUN Election (BOI18_election) C++14
100 / 100
 908 ms 86184 KB 
/*
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;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 88 ms 12152 KB Output is correct
7 Correct 79 ms 12152 KB Output is correct
8 Correct 88 ms 12152 KB Output is correct
9 Correct 76 ms 12152 KB Output is correct
10 Correct 92 ms 12024 KB Output is correct
11 Correct 88 ms 12280 KB Output is correct
12 Correct 91 ms 12408 KB Output is correct
13 Correct 89 ms 12280 KB Output is correct
14 Correct 87 ms 12152 KB Output is correct
15 Correct 88 ms 12152 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 88 ms 12152 KB Output is correct
7 Correct 79 ms 12152 KB Output is correct
8 Correct 88 ms 12152 KB Output is correct
9 Correct 76 ms 12152 KB Output is correct
10 Correct 92 ms 12024 KB Output is correct
11 Correct 88 ms 12280 KB Output is correct
12 Correct 91 ms 12408 KB Output is correct
13 Correct 89 ms 12280 KB Output is correct
14 Correct 87 ms 12152 KB Output is correct
15 Correct 88 ms 12152 KB Output is correct
16 Correct 894 ms 85132 KB Output is correct
17 Correct 754 ms 84616 KB Output is correct
18 Correct 821 ms 84876 KB Output is correct
19 Correct 669 ms 84364 KB Output is correct
20 Correct 897 ms 84236 KB Output is correct
21 Correct 908 ms 85892 KB Output is correct
22 Correct 903 ms 85796 KB Output is correct
23 Correct 902 ms 86184 KB Output is correct
24 Correct 900 ms 85812 KB Output is correct
25 Correct 903 ms 85348 KB Output is correct