QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#591634#8338. Quad Kingdoms ChessDBsoleilWA 35ms14956kbC++231.9kb2024-09-26 16:57:202024-09-26 16:57:21

Judging History

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

  • [2024-09-26 16:57:21]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:14956kb
  • [2024-09-26 16:57:20]
  • 提交

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]);
    int mid = (l + r) >> 1;
    cur[p] = get(ls, l, mid, 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

詳細信息

Test #1:

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

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: 33ms
memory: 14892kb

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: 28ms
memory: 14956kb

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: 35ms
memory: 14956kb

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
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:

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