QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463334 | #8335. Fast Hash Transform | PlentyOfPenalty# | WA | 1ms | 5716kb | C++20 | 1.9kb | 2024-07-04 18:18:34 | 2024-07-04 18:18:36 |
Judging History
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'