Submission #1127411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127411		VinhLuu	Election (BOI18_election)	C++20	100 / 100	454 ms	22388 KiB

election

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

const int N = 1e6 + 5;
const int oo = 1e9;

int n, q, a[N];

struct node {
  int le, ri, kq, val;
} st[N << 2];

node me(node _left, node _right) {
  node now = {0, 0, 0, 0};
  now.val = _left.val + _right.val;
  now.le = max(_left.le, _left.val + _right.le);
  now.ri = max(_right.ri, _right.val + _left.ri);
  now.kq = max({_left.le + _right.ri, _left.kq + _right.val, _right.kq + _left.val});
  return now;
}

void build(int i,int l,int r) {
  if(l == r) {
    if(a[l] == 1) st[i] = {1, 1, 1, 1};
    else st[i] = {0, 0, -1, -1};
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build(i << 1|1, mid + 1, r);
  st[i] = me(st[i << 1], st[i << 1|1]);
//  cerr << i << " " << l << " " << r << "\n";
//  cerr << st[i].le << " " << st[i].ri << " " << st[i].kq << " " << st[i].val << " h\n";
}

node get(int i,int l,int r,int u,int v) {
  if(l > r || r < u || v < l) return {0, 0, 0, 0};
  if(u <= l && r <= v) return st[i];
  int mid = (l + r) / 2;
  return me(get(i << 1, l, mid, u, v), get(i << 1|1, mid + 1, r, u, v));
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n;
  string str; cin >> str;
  str = " " + str;
  for(int i = 1; i <= n; i ++) {
    if(str[i] == 'C') a[i] = -1;
    else a[i] = 1;
  }
  build(1, 1, n);
  cin >> q;
  while(q--) {
    int l, r; cin >> l >> r;
    cout << get(1, 1, n, l, r).kq << "\n";
  }
}
#endif // lpv

Compilation message (stderr)

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

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