QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#375498#8338. Quad Kingdoms ChessisaunoyaWA 40ms3832kbC++233.5kb2024-04-03 11:31:162024-04-03 11:31:17

Judging History

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

  • [2024-04-03 11:31:17]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:3832kb
  • [2024-04-03 11:31:16]
  • 提交

answer

#if defined(LOCAL)
#include <D:/cp/templates/my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
#define debug(...) 42
#define rep1(a) for (auto i = 0; i < a; i++)
#define rep2(i, a) for (auto i = 0; i < a; i++)
#define rep3(i, a, b) for (auto i = a; i < b; i++)
#define rep4(i, a, b, c) for (auto i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
template <typename T> using vc = vector<T>;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937 rng(2813289);
const int INF = 1000000000;
const ll LNF = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
#endif

// using ull = unsigned long long;

const int mod = 1e9 + 7;
map<int, ll> foo;
vi get_stk(vi a) {
  vi stk;
  for (auto ai : a) {
    while (!stk.empty() && stk.back() < ai) {
      stk.pop_back();
    }
    stk.pb(ai);
  }
  return stk;
}

struct array {
  int n;
  vi a;
  array() {}
  array(int N) { n = N; }
  void init(int N) {
    n = N;
    a.resize(n);
    rep(i, n) cin >> a[i];
    rep(i, n) {
      if (!foo.count(a[i])) {
        foo[a[i]] = rng();
      }
    }
    leaf.resize(n * 4);
    mx.resize(n * 4);
    tr.resize(n * 4);
    build(0, n, 1);
  }
  vi leaf, mx;
  vc<ll> tr;
  ll calc(int p, int x) {
    if (x > mx[p]) {
      return 1;
    } else if (leaf[p]) {
      if (x <= mx[p]) {
        return foo[mx[p]];
      } else {
        return 1;
      }
    }

    if (x > mx[p * 2 + 1]) { // x <= mx[p * 2]
      return calc(p * 2, x);
    } else { // x <= mx[p * 2 + 1]
      return tr[p] * calc(p * 2 + 1, x) % mod;
    }
  }
  void pull(int p) {
    mx[p] = max(mx[p * 2], mx[p * 2 + 1]);
    tr[p] = calc(p * 2, mx[p * 2 + 1]);
  }
  void build(int l, int r, int p) {
    if (r - l == 1) {
      leaf[p] = 1;
      mx[p] = a[l];
      return;
    }
    int m = (l + r) / 2;
    build(l, m, p * 2);
    build(m, r, p * 2 + 1);
    pull(p);
  }

  void modify(int l, int r, int p, int x, int v) {
    if (r - l == 1) {
      leaf[p] = 1;
      mx[p] = v;
      return;
    }
    int m = (l + r) / 2;
    if (x < m) {
      modify(l, m, p * 2, x, v);
    } else {
      modify(m, r, p * 2 + 1, x, v);
    }
    pull(p);
  }

  void modify(int x, int y) {
    a[x] = y;
    modify(0, n, 1, x, y);
  }

  ll sol() { return calc(1, -1); }

  // void modify(int x, int y) { a[x] = y; }
  // vi stk() { return get_stk(a); }

} a[2];

void solve() {
  int n[2];
  cin >> n[0];
  a[0].init(n[0]);
  cin >> n[1];
  a[1].init(n[1]);
  int Q;
  cin >> Q;
  while (Q--) {
    int p, x, y;
    cin >> p >> x >> y;
    --p;
    --x;
    if (!foo.count(y)) {
      foo[y] = rng();
    }
    a[p].modify(x, y);
    // cout << (a[0].stk() == a[1].stk() ? "YES" : "NO") << "\n";
    cout << (a[0].sol() == a[1].sol() ? "YES" : "NO") << "\n";
  }
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

input:

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

output:

NO
NO
NO
YES
NO
NO
NO
YES

result:

ok 8 tokens

Test #2:

score: 0
Accepted
time: 35ms
memory: 3832kb

input:

1
2
6
2 1 1 1 1 1
200000
2 6 2
1 1 1
1 1 1
1 1 2
2 1 1
1 1 2
1 1 1
2 4 1
2 1 2
1 1 1
1 1 2
2 5 1
1 1 1
1 1 2
1 1 1
2 6 1
1 1 2
1 1 2
1 1 2
2 3 1
1 1 1
2 1 1
2 6 2
1 1 2
2 4 1
1 1 2
2 6 1
1 1 2
1 1 1
2 5 2
2 6 2
1 1 1
2 4 2
2 5 2
2 6 2
1 1 1
2 5 1
2 6 2
1 1 2
1 1 1
1 1 1
2 4 1
1 1 2
1 1 2
1 1 2
2 3 2...

output:

NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

ok 200000 tokens

Test #3:

score: 0
Accepted
time: 34ms
memory: 3604kb

input:

6
2 1 1 2 1 2
1
1
200000
2 1 1
1 1 2
1 1 1
2 1 2
2 1 1
2 1 1
2 1 2
2 1 2
1 1 2
1 3 1
1 6 2
1 5 2
1 4 2
1 3 1
2 1 2
1 4 2
1 4 2
2 1 2
2 1 2
1 3 1
1 6 1
1 1 2
2 1 1
1 6 1
1 3 1
1 5 2
1 6 2
1 5 2
2 1 2
1 2 1
1 5 2
2 1 1
2 1 1
1 6 1
2 1 2
2 1 1
1 3 2
2 1 1
1 6 1
1 4 2
1 2 1
1 1 1
2 1 1
1 2 1
1 6 2
1 6 2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 200000 tokens

Test #4:

score: -100
Wrong Answer
time: 40ms
memory: 3648kb

input:

6
1 3 1 2 1 2
6
2 1 3 3 3 1
200000
2 4 2
1 2 1
1 6 2
2 3 2
1 1 1
1 6 2
1 6 2
1 3 2
2 6 1
2 4 3
1 1 2
2 5 2
2 6 2
2 3 1
1 4 3
1 3 1
2 5 2
2 4 2
2 1 3
1 1 1
2 2 2
2 4 2
1 5 3
1 6 3
2 6 3
1 5 3
2 5 3
2 4 1
2 4 2
1 1 2
1 6 1
2 6 1
1 2 3
1 1 3
1 1 1
2 6 3
2 4 1
1 4 2
2 2 1
1 3 1
1 1 3
1 1 3
1 4 3
1 3 3
2...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer 180th words differ - expected: 'YES', found: 'NO'