oj.uz

Submission #736764

# Submission time Handle Problem Language Result Execution time Memory
736764 2023-05-06T08:02:08 Z veehz Crossing (JOI21_crossing) C++17
26 / 100
 3972 ms 23184 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back

/* Segment Tree */
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
  /* S op(S a, S b) {} -> Combine values */
  /* S e() {} -> Initial value (0) */
  int _n;
  vector<S> d;
  segtree() : segtree(0) {}
  explicit segtree(int n) : segtree(vector<S>(n, e())) {}
  explicit segtree(vector<S> v) : _n(int(v.size())) {
    d.assign(4 * _n, e());
    if(_n) build(v);
  }
  void build(vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      d[v] = op(d[v * 2], d[v * 2 + 1]);
    }
  }
  void set(int pos, S new_val, int tl = 0, int tr = -1, int v = 1) {
    assert(0 <= pos && pos < _n);
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        set(pos, new_val, tl, tm, v * 2);
      else
        set(pos, new_val, tm + 1, tr, v * 2 + 1);
      d[v] = op(d[2 * v], d[2 * v + 1]);
    }
  }
  S prod(int l, int r, int tl = 0, int tr = -1, int v = 1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return e();
    if (l == tl && r == tr) return d[v];
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), tl, tm, 2 * v),
              prod(max(l, tm + 1), r, tm + 1, tr, 2 * v + 1));
  }
  // new - might have bugs
  size_t prod_lower_bound(S x, int tl = 0, int tr = -1, int v = 1,
                          S acc = e()) {
    if (tr == -1) {
      if (prod(0, _n - 1) < x) return _n;
      tr = _n - 1;
    }
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (op(acc, d[2 * v]) < x)
      return prod_lower_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v]));
    else
      return prod_lower_bound(x, tl, tm, 2 * v, acc);
  }
  size_t prod_upper_bound(S x, int tl = 0, int tr = -1, int v = 1,
                          S acc = e()) {
    if (tr == -1) {
      if (prod(0, _n - 1) <= x) return _n;
      tr = _n - 1;
    }
    if (tl == tr) return tl;
    int tm = (tl + tr) / 2;
    if (op(acc, d[2 * v]) <= x)
      return prod_upper_bound(x, tm + 1, tr, 2 * v + 1, op(acc, d[2 * v]));
    else
      return prod_upper_bound(x, tl, tm, 2 * v, acc);
  }
};
/* End: Segment Tree */

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct lazySegtree {
  int _n;
  vector<S> d;
  vector<F> lz;
  lazySegtree() : lazySegtree(0) {}
  lazySegtree(int n) : lazySegtree(vector<S>(n, e())) {}
  lazySegtree(vector<S> a)
      : _n((int)a.size()), d(4 * (int)a.size()), lz(4 * (int)a.size(), id()) {
    build(a);
  }

  void build(const vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, 2 * v, tl, tm);
      build(a, 2 * v + 1, tm + 1, tr);
      d[v] = op(d[2 * v], d[2 * v + 1]);
    }
  }

  void apply(int v, F f) {
    d[v] = mapping(f, d[v]);
    lz[v] = composition(f, lz[v]);
  }

  void push(int v) {
    apply(2 * v, lz[v]);
    apply(2 * v + 1, lz[v]);
    lz[v] = id();
  }

  void update(int v) { d[v] = op(d[2 * v], d[2 * v + 1]); }

  void set(int pos, S val, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;

    if (tl == tr) {
      d[v] = val;
    } else {
      int tm = (tl + tr) / 2;
      push(v);
      if (pos <= tm) {
        set(pos, val, 2 * v, tl, tm);
      } else {
        set(pos, val, 2 * v + 1, tm + 1, tr);
      }
      update(v);
    }
  }

  /** Apply to [l,r] */
  void apply(int l, int r, F f, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return;

    if (l == tl && r == tr) {
      apply(v, f);
    } else {
      push(v);
      int tm = (tl + tr) / 2;
      apply(l, min(r, tm), f, 2 * v, tl, tm);
      apply(max(l, tm + 1), r, f, 2 * v + 1, tm + 1, tr);
      update(v);
    }
  }

  /** a[l] x a[l+1] x ... x a[r] */
  S prod(int l, int r, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (r < l) return e();

    if (l == tl && r == tr) return d[v];

    push(v);
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), 2 * v, tl, tm),
              prod(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr));
  }
};

// for comparing sa (= sb = sc)
struct sk {
  array<bool, 3> x;
  sk() : x({0, 0, 0}) {}
};

sk skop(sk a, sk b) {
  sk c;
  for (int i = 0; i < 3; i++) c.x[i] = (a.x[i] || b.x[i]);
  return c;
}
sk ske() { return sk(); }

segtree<sk, skop, ske> st;

struct S {
  bool val;
  int l, r;
};
S op(S a, S b) { return {a.val && b.val, min(a.l, b.l), max(a.r, b.r)}; }
S e() { return {true, INT_MAX, INT_MIN}; }

typedef int F;
// 0 = none
// 1 = J, 2 = O, 3 = I
S mapping(F f, S x) {
  if (f == 0) return x;
  f--;
  auto r = st.prod(x.l, x.r).x;
  if (r[f] && (r[0] + r[1] + r[2] == 1)) {
    return {true, x.l, x.r};
  }
  return {false, x.l, x.r};
}

F composition(F f, F g) {
  if (f == 0) return g;
  return f;
}

F id() { return 0; }

int main() {
  int n;
  cin >> n;

  // s[a] = s[b] = s[c]
  string s;
  cin >> s >> s >> s;
  vector<sk> skvec(n);
  for (int i = 0; i < n; i++) {
    skvec[i].x = {s[i] == 'J', s[i] == 'O', s[i] == 'I'};
  }
  st = segtree<sk, skop, ske>(skvec);

  int q;
  cin >> q;
  string t;
  cin >> t;
  vector<S> svec(n);
  for (int i = 0; i < n; i++) {
    svec[i] = {t[i] == s[i], i, i};
  }

  lazySegtree<S, op, e, F, mapping, composition, id> seg(svec);
  cout << (seg.prod(0, n - 1).val ? "Yes" : "No") << endl;
  while (q--) {
    int l, r;
    char c;
    cin >> l >> r >> c;
    int f = 0;
    if (c == 'J') f = 1;
    if (c == 'O') f = 2;
    if (c == 'I') f = 3;

    seg.apply(l - 1, r - 1, f);
    cout << (seg.prod(0, n - 1).val ? "Yes" : "No") << endl;
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 972 KB Output is correct
2 Correct 652 ms 968 KB Output is correct
3 Correct 644 ms 1060 KB Output is correct
4 Correct 511 ms 996 KB Output is correct
5 Correct 528 ms 2388 KB Output is correct
6 Correct 546 ms 2412 KB Output is correct
7 Correct 550 ms 2364 KB Output is correct
8 Correct 560 ms 2368 KB Output is correct
9 Correct 562 ms 2484 KB Output is correct
10 Correct 537 ms 2348 KB Output is correct
11 Correct 564 ms 2400 KB Output is correct
12 Correct 569 ms 2380 KB Output is correct
13 Correct 556 ms 2384 KB Output is correct
14 Correct 547 ms 2368 KB Output is correct
15 Correct 556 ms 2348 KB Output is correct
16 Correct 566 ms 2380 KB Output is correct
17 Correct 569 ms 2316 KB Output is correct
18 Correct 650 ms 2232 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 972 KB Output is correct
2 Correct 652 ms 968 KB Output is correct
3 Correct 644 ms 1060 KB Output is correct
4 Correct 511 ms 996 KB Output is correct
5 Correct 528 ms 2388 KB Output is correct
6 Correct 546 ms 2412 KB Output is correct
7 Correct 550 ms 2364 KB Output is correct
8 Correct 560 ms 2368 KB Output is correct
9 Correct 562 ms 2484 KB Output is correct
10 Correct 537 ms 2348 KB Output is correct
11 Correct 564 ms 2400 KB Output is correct
12 Correct 569 ms 2380 KB Output is correct
13 Correct 556 ms 2384 KB Output is correct
14 Correct 547 ms 2368 KB Output is correct
15 Correct 556 ms 2348 KB Output is correct
16 Correct 566 ms 2380 KB Output is correct
17 Correct 569 ms 2316 KB Output is correct
18 Correct 650 ms 2232 KB Output is correct
19 Correct 3629 ms 22984 KB Output is correct
20 Correct 3972 ms 22960 KB Output is correct
21 Correct 1405 ms 21680 KB Output is correct
22 Correct 1533 ms 19808 KB Output is correct
23 Correct 1189 ms 4224 KB Output is correct
24 Correct 1112 ms 4228 KB Output is correct
25 Correct 1520 ms 22964 KB Output is correct
26 Correct 1849 ms 22984 KB Output is correct
27 Correct 2548 ms 23032 KB Output is correct
28 Correct 2371 ms 22964 KB Output is correct
29 Correct 3174 ms 22428 KB Output is correct
30 Correct 1441 ms 4216 KB Output is correct
31 Correct 2321 ms 22972 KB Output is correct
32 Correct 2000 ms 21200 KB Output is correct
33 Correct 1098 ms 4268 KB Output is correct
34 Correct 2201 ms 23000 KB Output is correct
35 Correct 1130 ms 17868 KB Output is correct
36 Correct 871 ms 4292 KB Output is correct
37 Correct 895 ms 4352 KB Output is correct
38 Correct 2705 ms 22832 KB Output is correct
39 Correct 833 ms 22980 KB Output is correct
40 Correct 1344 ms 16492 KB Output is correct
41 Correct 3281 ms 23184 KB Output is correct
42 Correct 387 ms 22412 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 972 KB Output is correct
2 Correct 652 ms 968 KB Output is correct
3 Correct 644 ms 1060 KB Output is correct
4 Correct 511 ms 996 KB Output is correct
5 Correct 528 ms 2388 KB Output is correct
6 Correct 546 ms 2412 KB Output is correct
7 Correct 550 ms 2364 KB Output is correct
8 Correct 560 ms 2368 KB Output is correct
9 Correct 562 ms 2484 KB Output is correct
10 Correct 537 ms 2348 KB Output is correct
11 Correct 564 ms 2400 KB Output is correct
12 Correct 569 ms 2380 KB Output is correct
13 Correct 556 ms 2384 KB Output is correct
14 Correct 547 ms 2368 KB Output is correct
15 Correct 556 ms 2348 KB Output is correct
16 Correct 566 ms 2380 KB Output is correct
17 Correct 569 ms 2316 KB Output is correct
18 Correct 650 ms 2232 KB Output is correct
19 Correct 592 ms 2268 KB Output is correct
20 Correct 572 ms 2276 KB Output is correct
21 Incorrect 528 ms 2440 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 972 KB Output is correct
2 Correct 652 ms 968 KB Output is correct
3 Correct 644 ms 1060 KB Output is correct
4 Correct 511 ms 996 KB Output is correct
5 Correct 528 ms 2388 KB Output is correct
6 Correct 546 ms 2412 KB Output is correct
7 Correct 550 ms 2364 KB Output is correct
8 Correct 560 ms 2368 KB Output is correct
9 Correct 562 ms 2484 KB Output is correct
10 Correct 537 ms 2348 KB Output is correct
11 Correct 564 ms 2400 KB Output is correct
12 Correct 569 ms 2380 KB Output is correct
13 Correct 556 ms 2384 KB Output is correct
14 Correct 547 ms 2368 KB Output is correct
15 Correct 556 ms 2348 KB Output is correct
16 Correct 566 ms 2380 KB Output is correct
17 Correct 569 ms 2316 KB Output is correct
18 Correct 650 ms 2232 KB Output is correct
19 Correct 3629 ms 22984 KB Output is correct
20 Correct 3972 ms 22960 KB Output is correct
21 Correct 1405 ms 21680 KB Output is correct
22 Correct 1533 ms 19808 KB Output is correct
23 Correct 1189 ms 4224 KB Output is correct
24 Correct 1112 ms 4228 KB Output is correct
25 Correct 1520 ms 22964 KB Output is correct
26 Correct 1849 ms 22984 KB Output is correct
27 Correct 2548 ms 23032 KB Output is correct
28 Correct 2371 ms 22964 KB Output is correct
29 Correct 3174 ms 22428 KB Output is correct
30 Correct 1441 ms 4216 KB Output is correct
31 Correct 2321 ms 22972 KB Output is correct
32 Correct 2000 ms 21200 KB Output is correct
33 Correct 1098 ms 4268 KB Output is correct
34 Correct 2201 ms 23000 KB Output is correct
35 Correct 1130 ms 17868 KB Output is correct
36 Correct 871 ms 4292 KB Output is correct
37 Correct 895 ms 4352 KB Output is correct
38 Correct 2705 ms 22832 KB Output is correct
39 Correct 833 ms 22980 KB Output is correct
40 Correct 1344 ms 16492 KB Output is correct
41 Correct 3281 ms 23184 KB Output is correct
42 Correct 387 ms 22412 KB Output is correct
43 Correct 592 ms 2268 KB Output is correct
44 Correct 572 ms 2276 KB Output is correct
45 Incorrect 528 ms 2440 KB Output isn't correct
46 Halted 0 ms 0 KB -