oj.uz

Submission #729261

# Submission time Handle Problem Language Result Execution time Memory
729261 2023-04-23T17:36:35 Z YENGOYAN Election (BOI18_election) C++17
100 / 100
 584 ms 20256 KB 
/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e9;
 
vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };

int n, q;
string s;

struct node {
  int l, r, sm, a;
};

vector<node> seg;

node merge(node left, node right) {
  node cur;
  cur.l = max(left.l, left.sm + right.l);
  cur.r = max(right.r, right.sm + left.r);
  cur.sm = left.sm + right.sm;
  cur.a = max({left.a + right.sm, left.sm + right.a, left.l + right.r});
  return cur;
}

void build(int lx, int rx, int u){
  if(lx == rx) {
    if(lx < n) {
      if(s[lx] == 'T') {
        seg[u].l = seg[u].r = seg[u].sm = seg[u].a = 1;
      }
      else {
        seg[u].l = seg[u].r = 0;
        seg[u].sm = -1;
        seg[u].a = 0;
      }
    }
    else {
      seg[u].l = seg[u].r = seg[u].sm = seg[u].a = 0;
    }
    return;
  }
  int m = (lx + rx) / 2;
  build(lx, m, 2 * u + 1), build(m + 1, rx, 2 * u + 2);
  seg[u] = merge(seg[2 * u + 1], seg[2 * u + 2]);
}

node get(int ll, int rr, int lx, int rx, int u){
  if(lx >= ll && rx <= rr){
    return seg[u];
  }
  if(lx > rr || rx < ll) {
    return {0, 0, 0, 0};
  }
  int m = (lx + rx) / 2;
  return merge(get(ll, rr, lx, m, 2 * u + 1), get(ll, rr, m + 1, rx, 2 * u + 2));
}

void solve() {
  cin >> n >> s >> q;
  int sz = 1;
  while(sz < n) {
    sz <<= 1;
  }
  seg = vector<node> (2 * sz);
  build(0, sz - 1, 0);
  while(q--){
    int l, r; cin >> l >> r;
    cout << get(l - 1, r - 1, 0, sz - 1, 0).a << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int t; cin >> t; while(t--)
    solve();
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 58 ms 4936 KB Output is correct
7 Correct 57 ms 4824 KB Output is correct
8 Correct 53 ms 4720 KB Output is correct
9 Correct 57 ms 4776 KB Output is correct
10 Correct 64 ms 4804 KB Output is correct
11 Correct 52 ms 4940 KB Output is correct
12 Correct 60 ms 4896 KB Output is correct
13 Correct 57 ms 4964 KB Output is correct
14 Correct 65 ms 4824 KB Output is correct
15 Correct 52 ms 4812 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 58 ms 4936 KB Output is correct
7 Correct 57 ms 4824 KB Output is correct
8 Correct 53 ms 4720 KB Output is correct
9 Correct 57 ms 4776 KB Output is correct
10 Correct 64 ms 4804 KB Output is correct
11 Correct 52 ms 4940 KB Output is correct
12 Correct 60 ms 4896 KB Output is correct
13 Correct 57 ms 4964 KB Output is correct
14 Correct 65 ms 4824 KB Output is correct
15 Correct 52 ms 4812 KB Output is correct
16 Correct 492 ms 19176 KB Output is correct
17 Correct 556 ms 19252 KB Output is correct
18 Correct 493 ms 19280 KB Output is correct
19 Correct 406 ms 18848 KB Output is correct
20 Correct 584 ms 18304 KB Output is correct
21 Correct 496 ms 20236 KB Output is correct
22 Correct 496 ms 20036 KB Output is correct
23 Correct 515 ms 20256 KB Output is correct
24 Correct 522 ms 19872 KB Output is correct
25 Correct 494 ms 19432 KB Output is correct