QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484530#8338. Quad Kingdoms Chess114514abcWA 60ms26416kbC++204.2kb2024-07-19 19:52:592024-07-19 19:52:59

Judging History

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

  • [2024-07-19 19:52:59]
  • 评测
  • 测评结果：WA
  • 用时：60ms
  • 内存：26416kb
查看
  • [2024-07-19 19:52:59]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using ULL = unsigned long long;

const int N = 1e6 + 5;

mt19937_64 rnd(time(0));

ULL c[N];
int n[3], a[3][N], q, op, v, x, id;

struct S_TREE{
  struct Se_lin{
    struct Node{
      int l, r, maxx;
    }t[N * 4];
    void renew(int p){
      t[p].maxx = max(t[p * 2].maxx, t[p * 2 + 1].maxx);
    }
    void build(int p, int l, int r){
      t[p].l = l, t[p].r = r, t[p].maxx = 0;
      if(l == r){
        return;
      }
      int mid = (l + r) >> 1;
      build(p * 2, l, mid);
      build(p * 2 + 1, mid + 1, r);
    }
    void updata(int p, int l, int x){
      if(t[p].l == t[p].r){
        t[p].maxx = x;
        return;
      }
      int mid = (t[p].l + t[p].r) >> 1;
      if(l <= mid){
        updata(p * 2, l, x);
      }
      else{
        updata(p * 2 + 1, l, x);
      }
      renew(p);
    }
    int getsum(int p, int x){
      if(t[p].l == t[p].r){
        return t[p].l;
      }
      if(t[p * 2 + 1].maxx >= x){
        return getsum(p * 2 + 1, x);
      }
      return getsum(p * 2, x);
    }
  }T;
  struct seg_li{
    struct Node{
      int l, r;
      ULL lazy;
      ULL data;
    }t[N * 4];
    void tog(int p, ULL L){
      t[p].lazy += L;
      t[p].data += L;
    }
    void Lazy(int p){
      tog(p * 2, t[p].lazy);
      tog(p * 2 + 1, t[p].lazy);
      t[p].lazy = 0;
    }
    void build(int p, int l, int r){
      t[p].l = l, t[p].r = r, t[p].data = t[p].lazy = 0;
      if(l == r){
        return;
      }
      int mid = (l + r) >> 1;
      build(p * 2, l, mid);
      build(p * 2 + 1, mid + 1, r);
    }
    void updata(int p, int l, int r, ULL L){
      if(t[p].l >= l && t[p].r <= r){
        tog(p, L);
        return;
      }
      Lazy(p);
      int mid = (t[p].l + t[p].r) >> 1;
      if(l <= mid){
        updata(p * 2, l, r, L);
      }
      if(r > mid){
        updata(p * 2 + 1, l, r, L);
      }
    }
    ULL getsum(int p, int l){
      if(t[p].l == t[p].r){
        return t[p].data;
      }
      Lazy(p);
      int mid = (t[p].l + t[p].r) >> 1;
      if(l <= mid){
        return getsum(p * 2, l);
      }
      return getsum(p * 2 + 1, l);
    }
  }Hash_T;
  struct Node{
    int l, r, maxx, id, last, lastl;
  }t[N * 4];
  void renew(int p){
    if(t[p * 2].maxx >= t[p * 2 + 1].maxx && t[p * 2 + 1].maxx != 1e9){
      id = T.getsum(p * 2, t[p * 2 + 1].maxx);
      t[p * 2 + 1].last = Hash_T.getsum(1, id);
      Hash_T.updata(1, t[p * 2 + 1].id, t[p * 2 + 1].r, t[p * 2 + 1].last);
      t[p * 2 + 1].lastl = t[p * 2 + 1].id;
    }
    t[p].maxx = max(t[p * 2].maxx, t[p * 2 + 1].maxx);
    t[p].id = (t[p * 2].maxx == t[p].maxx ? t[p * 2].id : t[p * 2 + 1].id);
  }
  void build(int p, int l, int r){
    t[p].l = l, t[p].r = r, t[p].maxx = 1e9, t[p].id = l, t[p].last = 0, t[p].lastl = l;
    if(l == r){
      return;
    }
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
  }
  void emp(int x){
    Hash_T.build(1, 1, x);
    build(1, 1, x);
    T.build(1, 1, x);
  }
  void updata(int p, int l, int u, int v){
    if(t[p].l == t[p].r){
      t[p].maxx = v;
      t[p].last = 0;
      Hash_T.updata(1, l, l, -Hash_T.getsum(1, l));
      Hash_T.updata(1, l, l, c[v]);
      T.updata(1, l, v);
      return;
    }
    Hash_T.updata(1, t[p * 2 + 1].lastl, t[p * 2 + 1].r, -t[p * 2 + 1].last);
    t[p * 2 + 1].last = 0;
    int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid){
      updata(p * 2, l, u, v);
    }
    else{
      updata(p * 2 + 1, l, u, v);
    }
    renew(p);
  }
  ULL modify(int p){
    return Hash_T.getsum(1, p);
  }
}T[3];

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  for(int i = 1; i <= 100000; ++i){
    c[i] = rnd();
  }
  for(int i = 1; i <= 2; ++i){
    cin >> n[i];
    for(int j = 1; j <= n[i]; j++){
      cin >> a[i][j];
    }
  }
  for(int i = 1; i <= 2; ++i){
    T[i].emp(n[i]);
    for(int j = 1; j <= n[i]; j++){
      T[i].updata(1, j, 0, a[i][j]);
    }
  }
  cin >> q;
  while(q--){
    cin >> op >> v >> x;
    T[op].updata(1, v, a[op][v], x);
    a[op][v] = x;
    cout << (T[1].modify(n[1]) == T[2].modify(n[2]) ? "YES\n" : "NO\n");
  }
  return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 26340kb

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: 39ms
memory: 24176kb

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: 29ms
memory: 24180kb

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: 60ms
memory: 26416kb

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'
English 繁體中文 简体中文

服务器时间: 2024-12-02 21:45:55 | 开源项目