QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112214#5466. Permutation Compression6arenWA 2ms3432kbC++178.2kb2023-06-10 17:46:212023-06-10 17:46:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-10 17:46:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3432kb
  • [2023-06-10 17:46:21]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <cp/debugger.hpp>
#else
#define debug(...) 42
#endif

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

typedef int64_t int64;
typedef pair<int, int> ii;

// source: https://github.com/ngthanhtrung23/ACM_Notebook_new/blob/master/DataStructure/LazySegTree.h
// Lazy Segment Tree, copied from AtCoder {{{
// Source: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
// Doc: https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html
//
// Notes:
// - Index of elements from 0
// - Range queries are [l, r-1]
// - composition(f, g) should return f(g())
//
// Tested:
// - https://oj.vnoi.info/problem/qmax2
// - https://oj.vnoi.info/problem/lites
// - (range set, add, mult, sum) https://oj.vnoi.info/problem/segtree_itmix
// - (range add (i-L)*A + B, sum) https://oj.vnoi.info/problem/segtree_itladder
// - https://atcoder.jp/contests/practice2/tasks/practice2_l
// - https://judge.yosupo.jp/problem/range_affine_range_sum

int ceil_pow2(int n) {
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}
template <class S,                 // node data type
          S (*op)(S, S),           // combine 2 nodes
          S (*e)(),                // identity element
          class F,                 // lazy propagation tag
          S (*mapping)(F, S),      // apply tag F on a node
          F (*composition)(F, F),  // combine 2 tags
          F (*id)()                // identity tag
          >
struct LazySegTree {
  LazySegTree() : LazySegTree(0) {}
  explicit LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {}
  explicit LazySegTree(const vector<S> &v) : _n((int)v.size()) {
    log = ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    lz = std::vector<F>(size, id());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }

  // 0 <= p < n
  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  // 0 <= p < n
  S get(int p) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return d[p];
  }

  // Get product in range [l, r-1]
  // 0 <= l <= r <= n
  // For empty segment (l == r) -> return e()
  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return e();

    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    S sml = e(), smr = e();
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }

    return op(sml, smr);
  }

  S all_prod() { return d[1]; }

  // 0 <= p < n
  void apply(int p, F f) {
    assert(0 <= p && p < _n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    d[p] = mapping(f, d[p]);
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  // Apply f on all elements in range [l, r-1]
  // 0 <= l <= r <= n
  void apply(int l, int r, F f) {
    assert(0 <= l && l <= r && r <= _n);
    if (l == r) return;

    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) all_apply(l++, f);
        if (r & 1) all_apply(--r, f);
        l >>= 1;
        r >>= 1;
      }
      l = l2;
      r = r2;
    }

    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  // Binary search on SegTree to find largest r:
  //    f(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
  //    f(op(a[l] .. a[r])) = false    (assuming op(..., a[n]), which is out of bound, is always false)
  // template <bool (*g)(S)>
  // int max_right(int l) {
  //   return max_right(l, [](S x) { return g(x); });
  // }

  // Binary search on SegTree to find largest r:
  //    g(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
  //    g(op(a[l] .. a[r])) = false    (assuming op(..., a[n]), which is out of bound, is always false)
  template <class G>
  int max_right(int l, G g) {
    assert(0 <= l && l <= _n);
    assert(g(e()));
    if (l == _n) return _n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!g(op(sm, d[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (g(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }

  // Binary search on SegTree to find smallest l:
  //    f(op(a[l] .. a[r-1])) = true      (assuming empty array is always true)
  //    f(op(a[l-1] .. a[r-1])) = false   (assuming op(a[-1], ..), which is out of bound, is always false)
  template <class G>
  int min_left(int r, G g) {
    assert(0 <= r && r <= _n);
    assert(g(e()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!g(op(d[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (g(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  int _n, size, log;
  vector<S> d;
  vector<F> lz;

  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  void all_apply(int k, F f) {
    d[k] = mapping(f, d[k]);
    if (k < size) lz[k] = composition(f, lz[k]);
  }
  void push(int k) {
    all_apply(2 * k, lz[k]);
    all_apply(2 * k + 1, lz[k]);
    lz[k] = id();
  }
};
// }}}

// Examples {{{
struct LazySegTreeOps {
  static const int NOT_ASSIGNED = -123123123;
  static int op(int lhs, int rhs) { return max(lhs, rhs); }
  static int e() { return INT_MIN; }
  static int mapping(int tag, int node) {
    if (tag == NOT_ASSIGNED) return node;
    return tag;
  }
  static int composition(int tag1, int tag2) { return tag1; }
  static int id() { return NOT_ASSIGNED; }
};
// LazySegTree<int, LazySegTreeOps::op, LazySegTreeOps::e, int, LazySegTreeOps::mapping, LazySegTreeOps::composition,
//             LazySegTreeOps::id>
//     seg_tree(a);
// }}}

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n), b(m);
  for (int &e : a) cin >> e, e--;
  for (int &e : b) cin >> e, e--;
  set<int> l;
  for (int i = 0; i < k; i++) {
    int x;
    cin >> x;
    l.insert(x);
  }
  LazySegTree<int, LazySegTreeOps::op, LazySegTreeOps::e, int, LazySegTreeOps::mapping, LazySegTreeOps::composition,
              LazySegTreeOps::id>
      seg_tree(a);
  vector<int> pos(n);
  for (int i = 0; i < n; i++) pos[a[i]] = i;
  for (int i = 0; i + 1 < m; i++) {
    if (pos[b[i]] > pos[b[i + 1]]) {
      cout << "NO\n";
      return;
    }
  }
  for (int e : b) {
    pos[e] = -1;
  }
  vector<int> removed;
  for (int e : a) {
    if (pos[e] != -1) removed.push_back(e);
  }
  sort(removed.rbegin(), removed.rend());
  for (int e : removed) {
    int right = seg_tree.max_right(pos[e], [&](int x) { return x <= e; });
    int left = seg_tree.min_left(pos[e] + 1, [&](int x) { return x <= e; }) - 1;
    int target = right - left - 1;
    auto it = l.upper_bound(target);
    if (it == l.begin()) {
      cout << "NO\n";
      return;
    }
    it--;
    l.erase(it);
    seg_tree.apply(pos[e], INT_MIN);
  }
  cout << "YES\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3408kb

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3432kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES...

result:

wrong answer 4th lines differ - expected: 'YES', found: 'NO'