QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463334#8335. Fast Hash TransformPlentyOfPenalty#WA 1ms5716kbC++201.9kb2024-07-04 18:18:342024-07-04 18:18:36

Judging History

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

  • [2024-07-04 18:18:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5716kb
  • [2024-07-04 18:18:34]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=2e4;
ull Lsh(int x,int y){
  if(!y)return x;
  return (x<<y)|(x>>64-y);
}
struct elem{
  ull C,a[64];
  void clear(){
    C=0;
    for(int i=0;i<64;++i)a[i]=0;
  }
  ull Calc(ull x){
    ull ret=C;
    for(int i=0;i<64;++i)ret^=Lsh(x,i)&a[i];
    return ret;
  }
  elem operator*(const elem&y)const{
    static elem ret;
    ret.clear();
    ret.C=y.C;
    for(int i=0;i<64;++i){
      ret.C^=Lsh(C,i)&y.a[i];
      for(int j=0;j<64;++j){
        ret.a[i+j&63]^=Lsh(a[j],i)&y.a[i];
      }
    }
    return ret;
  }
}t[(N<<2)+10],ar[N+10],tmp;
int n,Q,C,m,op,sh;
int ql,qr,id;
ull B,v,qx;
void Upd(int x){
  t[x]=t[x<<1]*t[x<<1|1];
}
void Build(int x,int l,int r){
  if(l==r)return(void)(t[x]=ar[l]);
  int mid=(l+r>>1);
  Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
  Upd(x);
}
void Modify(int x,int l,int r,int id,elem&mv){
  if(l==r)return(void)(t[x]=mv);
  int mid=(l+r>>1);
  if(id<=mid)Modify(x<<1,l,mid,id,mv);
  else Modify(x<<1|1,mid+1,r,id,mv);
  Upd(x);
}
ull Query(int x,int l,int r,int nl,int nr,ull nw){
  if(l>nr||nl>r)return nw;
  if(nl<=l&&r<=nr)return t[x].Calc(nw);
  int mid=(l+r>>1);
  return Query(x<<1|1,mid+1,r,nl,nr,Query(x<<1,l,mid,nl,nr,nw));
}
int main(){
  //freopen("H2.in","r",stdin);
  cin.sync_with_stdio(0),cin.tie(0);
  cin>>n>>Q>>C;
  for(int i=1;i<=n;++i){
    cin>>m;
    for(int j=1;j<=m;++j){
      cin>>sh>>op>>v;
      if(!op)ar[i].C^=v,v=~v;
      ar[i].a[sh]=v;
    }
    cin>>B;
    ar[i].C^=B;
  }
  Build(1,1,n);
  while(Q--){
    cin>>op;
    if(!op){
      cin>>ql>>qr>>qx;
      cout<<Query(1,1,n,ql,qr,qx)<<"\n";
    }else{
      cin>>id;
      tmp.clear();
      cin>>m;
      for(int j=1;j<=m;++j){
        cin>>sh>>op>>v;
        if(!op)tmp.C^=v,v=~v;
        tmp.a[sh]=v;
      }
      cin>>B;
      tmp.C^=B;
      Modify(1,1,n,id,tmp);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5716kb

input:

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

output:

64206
2023
31
1112

result:

ok 4 tokens

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 5668kb

input:

9 9 3
32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...

output:

11296789428255913117
11296789428881332117
3374706643533967434
11296789428952827493
2722115909910444543
6515929019847752613

result:

wrong answer 1st words differ - expected: '9487331362121050549', found: '11296789428255913117'