oj.uz

Submission #736804

# Submission time Handle Problem Language Result Execution time Memory
736804 2023-05-06T08:41:52 Z veehz Crossing (JOI21_crossing) C++17
49 / 100
 7000 ms 92756 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(); }

inline segtree<sk, skop, ske> generateSegtree(string s) {
  const int n = s.size();
  vector<sk> skvec(n);
  for (int i = 0; i < n; i++) {
    skvec[i].x = {s[i] == 'J', s[i] == 'O', s[i] == 'I'};
  }
  return segtree<sk, skop, ske>(skvec);
}
vector<segtree<sk, skop, ske>> segtrees;

struct S {
  vector<bool> val;
  int l, r;
  bool compress() {
    for (int i = 0; i < (int)val.size(); i++)
      if (val[i]) return true;
    return false;
  }
};
S op(S a, S b) {
  vector<bool> v(segtrees.size());
  for (int i = 0; i < (int)segtrees.size(); i++) v[i] = (a.val[i] && b.val[i]);
  return {v, min(a.l, b.l), max(a.r, b.r)};
}
S e() { return {vector<bool>(segtrees.size(), 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--;
  vector<bool> v;
  for (int i = 0; i < (int)segtrees.size(); i++) {
    auto r = segtrees[i].prod(x.l, x.r).x;
    if (r[f] && (r[0] + r[1] + r[2] == 1))
      v.pb(true);
    else
      v.pb(false);
  }
  return {v, x.l, x.r};
}

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

F id() { return 0; }

string cross(string a, string b) {
  string c;
  for (int i = 0; i < (int)a.size(); i++) {
    if (a[i] == b[i])
      c.pb(a[i]);
    else if (a[i] == 'J' && b[i] == 'O')
      c.pb('I');
    else if (a[i] == 'J' && b[i] == 'I')
      c.pb('O');
    else if (a[i] == 'O' && b[i] == 'J')
      c.pb('I');
    else if (a[i] == 'O' && b[i] == 'I')
      c.pb('J');
    else if (a[i] == 'I' && b[i] == 'J')
      c.pb('O');
    else if (a[i] == 'I' && b[i] == 'O')
      c.pb('J');
  }
  return c;
}

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

  set<string> s;
  for (int i = 0; i < 3; i++) {
    string t;
    cin >> t;
    s.insert(t);
  }

  while (true) {
    vector<string> v;
    for (auto& t : s) v.pb(t);
    bool hasNew = false;
    for (int i = 0; i < (int)v.size(); i++) {
      for (int j = i + 1; j < (int)v.size(); j++) {
        string t = cross(v[i], v[j]);
        if (s.find(t) == s.end()) {
          s.insert(t);
          hasNew = true;
        }
      }
    }
    if (!hasNew) break;
  }
  vector<string> v;
  for (auto& t : s) v.pb(t);
  for (auto& t : v) segtrees.pb(generateSegtree(t));

  int q;
  cin >> q;
  string t;
  cin >> t;
  vector<S> svec(n);
  for (int i = 0; i < n; i++) {
    vector<bool> tmp(v.size());
    for (int j = 0; j < (int)v.size(); j++){
      tmp[j] = v[j][i] == t[i];
    }
    svec[i] = {tmp, i, i};
  }

  lazySegtree<S, op, e, F, mapping, composition, id> seg(svec);

  cout << (seg.prod(0, n - 1).compress() ? "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).compress() ? "Yes" : "No") << endl;
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 2272 KB Output is correct
2 Correct 1142 ms 2416 KB Output is correct
3 Correct 1217 ms 2296 KB Output is correct
4 Correct 935 ms 2372 KB Output is correct
5 Correct 915 ms 2348 KB Output is correct
6 Correct 877 ms 2320 KB Output is correct
7 Correct 898 ms 2356 KB Output is correct
8 Correct 955 ms 2380 KB Output is correct
9 Correct 925 ms 2552 KB Output is correct
10 Correct 927 ms 2440 KB Output is correct
11 Correct 949 ms 2508 KB Output is correct
12 Correct 916 ms 2368 KB Output is correct
13 Correct 950 ms 2524 KB Output is correct
14 Correct 956 ms 2372 KB Output is correct
15 Correct 914 ms 2540 KB Output is correct
16 Correct 935 ms 2444 KB Output is correct
17 Correct 880 ms 2448 KB Output is correct
18 Correct 1152 ms 2304 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 2272 KB Output is correct
2 Correct 1142 ms 2416 KB Output is correct
3 Correct 1217 ms 2296 KB Output is correct
4 Correct 935 ms 2372 KB Output is correct
5 Correct 915 ms 2348 KB Output is correct
6 Correct 877 ms 2320 KB Output is correct
7 Correct 898 ms 2356 KB Output is correct
8 Correct 955 ms 2380 KB Output is correct
9 Correct 925 ms 2552 KB Output is correct
10 Correct 927 ms 2440 KB Output is correct
11 Correct 949 ms 2508 KB Output is correct
12 Correct 916 ms 2368 KB Output is correct
13 Correct 950 ms 2524 KB Output is correct
14 Correct 956 ms 2372 KB Output is correct
15 Correct 914 ms 2540 KB Output is correct
16 Correct 935 ms 2444 KB Output is correct
17 Correct 880 ms 2448 KB Output is correct
18 Correct 1152 ms 2304 KB Output is correct
19 Correct 5868 ms 88300 KB Output is correct
20 Correct 6151 ms 88768 KB Output is correct
21 Correct 2780 ms 83472 KB Output is correct
22 Correct 2758 ms 75008 KB Output is correct
23 Correct 1558 ms 7352 KB Output is correct
24 Correct 1542 ms 7172 KB Output is correct
25 Correct 2611 ms 88728 KB Output is correct
26 Correct 3179 ms 88672 KB Output is correct
27 Correct 3695 ms 88732 KB Output is correct
28 Correct 4072 ms 88720 KB Output is correct
29 Correct 3487 ms 86200 KB Output is correct
30 Correct 2057 ms 7324 KB Output is correct
31 Correct 3864 ms 88724 KB Output is correct
32 Correct 3373 ms 80816 KB Output is correct
33 Correct 1594 ms 7228 KB Output is correct
34 Correct 3621 ms 88732 KB Output is correct
35 Correct 2289 ms 66092 KB Output is correct
36 Correct 1551 ms 7156 KB Output is correct
37 Correct 1610 ms 7200 KB Output is correct
38 Correct 4637 ms 88708 KB Output is correct
39 Correct 1665 ms 88716 KB Output is correct
40 Correct 2600 ms 58332 KB Output is correct
41 Correct 6003 ms 88748 KB Output is correct
42 Correct 530 ms 88736 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 2272 KB Output is correct
2 Correct 1142 ms 2416 KB Output is correct
3 Correct 1217 ms 2296 KB Output is correct
4 Correct 935 ms 2372 KB Output is correct
5 Correct 915 ms 2348 KB Output is correct
6 Correct 877 ms 2320 KB Output is correct
7 Correct 898 ms 2356 KB Output is correct
8 Correct 955 ms 2380 KB Output is correct
9 Correct 925 ms 2552 KB Output is correct
10 Correct 927 ms 2440 KB Output is correct
11 Correct 949 ms 2508 KB Output is correct
12 Correct 916 ms 2368 KB Output is correct
13 Correct 950 ms 2524 KB Output is correct
14 Correct 956 ms 2372 KB Output is correct
15 Correct 914 ms 2540 KB Output is correct
16 Correct 935 ms 2444 KB Output is correct
17 Correct 880 ms 2448 KB Output is correct
18 Correct 1152 ms 2304 KB Output is correct
19 Correct 2759 ms 2560 KB Output is correct
20 Correct 2873 ms 2376 KB Output is correct
21 Correct 1173 ms 2652 KB Output is correct
22 Correct 924 ms 2316 KB Output is correct
23 Correct 1103 ms 2428 KB Output is correct
24 Correct 1071 ms 2380 KB Output is correct
25 Correct 1115 ms 2392 KB Output is correct
26 Correct 1010 ms 2420 KB Output is correct
27 Correct 1204 ms 2500 KB Output is correct
28 Correct 1006 ms 2408 KB Output is correct
29 Correct 1258 ms 2552 KB Output is correct
30 Correct 1046 ms 2168 KB Output is correct
31 Correct 1976 ms 2460 KB Output is correct
32 Correct 1921 ms 2524 KB Output is correct
33 Correct 2136 ms 2460 KB Output is correct
34 Correct 1735 ms 2208 KB Output is correct
35 Correct 1904 ms 2364 KB Output is correct
36 Correct 2375 ms 2436 KB Output is correct
37 Correct 1898 ms 2464 KB Output is correct
38 Correct 2093 ms 2512 KB Output is correct
39 Correct 1946 ms 2392 KB Output is correct
40 Correct 2025 ms 2456 KB Output is correct
41 Correct 2122 ms 2348 KB Output is correct
42 Correct 2180 ms 2472 KB Output is correct
43 Correct 1815 ms 2372 KB Output is correct
44 Correct 1927 ms 2468 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 2272 KB Output is correct
2 Correct 1142 ms 2416 KB Output is correct
3 Correct 1217 ms 2296 KB Output is correct
4 Correct 935 ms 2372 KB Output is correct
5 Correct 915 ms 2348 KB Output is correct
6 Correct 877 ms 2320 KB Output is correct
7 Correct 898 ms 2356 KB Output is correct
8 Correct 955 ms 2380 KB Output is correct
9 Correct 925 ms 2552 KB Output is correct
10 Correct 927 ms 2440 KB Output is correct
11 Correct 949 ms 2508 KB Output is correct
12 Correct 916 ms 2368 KB Output is correct
13 Correct 950 ms 2524 KB Output is correct
14 Correct 956 ms 2372 KB Output is correct
15 Correct 914 ms 2540 KB Output is correct
16 Correct 935 ms 2444 KB Output is correct
17 Correct 880 ms 2448 KB Output is correct
18 Correct 1152 ms 2304 KB Output is correct
19 Correct 5868 ms 88300 KB Output is correct
20 Correct 6151 ms 88768 KB Output is correct
21 Correct 2780 ms 83472 KB Output is correct
22 Correct 2758 ms 75008 KB Output is correct
23 Correct 1558 ms 7352 KB Output is correct
24 Correct 1542 ms 7172 KB Output is correct
25 Correct 2611 ms 88728 KB Output is correct
26 Correct 3179 ms 88672 KB Output is correct
27 Correct 3695 ms 88732 KB Output is correct
28 Correct 4072 ms 88720 KB Output is correct
29 Correct 3487 ms 86200 KB Output is correct
30 Correct 2057 ms 7324 KB Output is correct
31 Correct 3864 ms 88724 KB Output is correct
32 Correct 3373 ms 80816 KB Output is correct
33 Correct 1594 ms 7228 KB Output is correct
34 Correct 3621 ms 88732 KB Output is correct
35 Correct 2289 ms 66092 KB Output is correct
36 Correct 1551 ms 7156 KB Output is correct
37 Correct 1610 ms 7200 KB Output is correct
38 Correct 4637 ms 88708 KB Output is correct
39 Correct 1665 ms 88716 KB Output is correct
40 Correct 2600 ms 58332 KB Output is correct
41 Correct 6003 ms 88748 KB Output is correct
42 Correct 530 ms 88736 KB Output is correct
43 Correct 2759 ms 2560 KB Output is correct
44 Correct 2873 ms 2376 KB Output is correct
45 Correct 1173 ms 2652 KB Output is correct
46 Correct 924 ms 2316 KB Output is correct
47 Correct 1103 ms 2428 KB Output is correct
48 Correct 1071 ms 2380 KB Output is correct
49 Correct 1115 ms 2392 KB Output is correct
50 Correct 1010 ms 2420 KB Output is correct
51 Correct 1204 ms 2500 KB Output is correct
52 Correct 1006 ms 2408 KB Output is correct
53 Correct 1258 ms 2552 KB Output is correct
54 Correct 1046 ms 2168 KB Output is correct
55 Correct 1976 ms 2460 KB Output is correct
56 Correct 1921 ms 2524 KB Output is correct
57 Correct 2136 ms 2460 KB Output is correct
58 Correct 1735 ms 2208 KB Output is correct
59 Correct 1904 ms 2364 KB Output is correct
60 Correct 2375 ms 2436 KB Output is correct
61 Correct 1898 ms 2464 KB Output is correct
62 Correct 2093 ms 2512 KB Output is correct
63 Correct 1946 ms 2392 KB Output is correct
64 Correct 2025 ms 2456 KB Output is correct
65 Correct 2122 ms 2348 KB Output is correct
66 Correct 2180 ms 2472 KB Output is correct
67 Correct 1815 ms 2372 KB Output is correct
68 Correct 1927 ms 2468 KB Output is correct
69 Execution timed out 7046 ms 92756 KB Time limit exceeded
70 Halted 0 ms 0 KB -