QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591602#8338. Quad Kingdoms ChessDBsoleilWA 30ms14892kbC++231.9kb2024-09-26 16:43:172024-09-26 16:43:17

Judging History

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

  • [2024-09-26 16:43:17]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:14892kb
  • [2024-09-26 16:43:17]
  • 提交

answer


#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e5 + 5, V = 1e5, MaxV = 1e5 + 5;
static uint64_t hmap[MaxV];
struct Array {
  int n, a[Maxn];
  int mx[Maxn << 2];
  uint64_t cur[Maxn << 2], hs[Maxn << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
  int get(int p, int l, int r, int w) {
    if (l == r) return mx[p] >= w ? hs[p] : 0;
    int mid = (l + r) >> 1;
    if (mx[rs] >= w) return cur[p] + get(rs, mid + 1, r, w);
    else return get(ls, l, mid, w);
  } // Array::get
  void pushup(int p, int l, int r) {
    mx[p] = max(mx[ls], mx[rs]);
    cur[p] = get(ls, l, r, mx[rs]);
    hs[p] = cur[p] + hs[rs];
  } // Array::pushup
  void apply(int p, int v) {
    mx[p] = v; cur[p] = 0, hs[p] = hmap[v];
  } // Array::apply
  void build(int p, int l, int r) {
    if (l == r) return apply(p, a[l]);
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p, l, r);
  } // Array::build
  void update(int p, int l, int r, int x) {
    if (l == r) return apply(p, a[l]);
    int mid = (l + r) >> 1;
    if (x <= mid) update(ls, l, mid, x);
    else update(rs, mid + 1, r, x);
    pushup(p, l, r);
  } // Array::update
  void update(int x, int v) { a[x] = v, update(1, 1, n, x); }
  void build(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
  } // Array::build
  uint64_t query(void) { return hs[1]; }
} a[2];
int main(void) {
  static mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
  for (int i = 1; i <= V; ++i) hmap[i] = gen64();
  a[1].build(); a[0].build();
  int qn; scanf("%d", &qn);
  while (qn--) {
    int i, x, y;
    scanf("%d%d%d", &i, &x, &y);
    a[i & 1].update(x, y);
    if (a[1].query() == a[0].query())
      printf("YES\n");
    else printf("NO\n");
  }
  return 0;
} // main

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 30ms
memory: 14832kb

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:

YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
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
N...

result:

wrong answer 1st words differ - expected: 'NO', found: 'YES'