QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#591652#8338. Quad Kingdoms ChessDBsoleilWA 35ms14952kbC++231.9kb2024-09-26 17:03:092024-09-26 17:03:11

Judging History

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

  • [2024-09-26 17:03:11]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:14952kb
  • [2024-09-26 17:03:09]
  • 提交

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

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: 0
Accepted
time: 29ms
memory: 14952kb

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: 32ms
memory: 14896kb

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

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'