QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#671752 | #8335. Fast Hash Transform | huan_yp | TL | 4170ms | 56352kb | C++20 | 4.4kb | 2024-10-24 14:20:28 | 2024-10-24 14:20:28 |
Judging History
answer
#include<bits/stdc++.h>
#define M 20005
#define mid ((l+r)>>1)
using namespace std;
struct IO {
static const int inSZ = 1 << 17;
char inBuf[inSZ], *in1, *in2;
template<class T> inline __attribute((always_inline))
T read() {
if (in1 > inBuf + inSZ - 32) [[unlikely]] {
auto len = in2 - in1;
memcpy(inBuf, in1, len);
in1 = inBuf, in2 = inBuf + len;
in2 += fread(in2, 1, inSZ - len, stdin);
if (in2 != inBuf + inSZ) *in2 = 0;
}
T res = 0;
unsigned char c;
while ((c = *in1++) < 48);
while (res = res * 10 + (c - 48), (c = *in1++) >= 48);
return res;
}
static const int outSZ = 1 << 21;
char outBuf[outSZ], *out;
template<class T> inline __attribute((always_inline))
void write(T x) {
if (out > outBuf + outSZ - 32) [[unlikely]]
fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
if (!x) return *out++ = 48, void();
if (x < 0) *out++ = 45, x = -x;
alignas(2) const char* digits =
"0001020304050607080910111213141516171819"
"2021222324252627282930313233343536373839"
"4041424344454647484950515253545556575859"
"6061626364656667686970717273747576777879"
"8081828384858687888990919293949596979899";
alignas(64) static char buf[20];
char* p = buf + 20;
while (x >= 10) memcpy(p -= 2, digits + x % 100 * 2, 2), x /= 100;
if (x) *--p = 48 + x;
auto len = buf + 20 - p;
memcpy(out, p, len), out += len;
}
void init() {
in1 = in2 = inBuf + inSZ;
out = outBuf;
}
~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;
template<class T = int> T read() {
return IO.read<T>();
}
template<class... Args> void read(Args&... args) {
((args = IO.read<Args>()), ...);
}
template<class T> void write(T x, char c = '\n') {
IO.write(x), *IO.out++ = c;
}
int n,q,c,m,s[M],o[M];
unsigned long long B,A[M];
struct node{
unsigned long long a[64];
bool x[64];
}a[M],sm[M<<2];
node add(const node &b,const node &a){
node ans({});
memcpy(ans.x, a.x, sizeof(a.x));
for(int i=0;i<=63;++i){
for(int j=0;j<=63;++j)
if((a.a[i]>>j)&1) ans.a[i]^=b.a[j],ans.x[i]^=b.x[j];
}
return ans;
}
node cj(){
node ans({});
for(int i=0;i<=63;++i){
ans.x[i]=((B>>i)&1);
for(int j=1;j<=m;++j){
if(((A[j]>>i)&1)&&o[j]==0){ans.x[i]^=1;continue;}
if((!((A[j]>>i)&1))&&o[j]==1) continue;
if(i>=s[j]) ans.a[i]^=(1ll<<(i-s[j]));
else ans.a[i]^=(1ll<<(64+i-s[j]));
}
}
return ans;
}
void build(int p,int l,int r){
if(l==r){sm[p]=a[l];return ;}
build(p<<1,l,mid);build(p<<1|1,mid+1,r);
sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
node ck(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return sm[p];
if(L>mid) return ck(p<<1|1,mid+1,r,L,R);
if(R<=mid) return ck(p<<1,l,mid,L,R);
return add(ck(p<<1,l,mid,L,R),ck(p<<1|1,mid+1,r,L,R));
}
void cg(int p,int l,int r,int pos){
if(l==r){sm[p]=a[l];return;}
if(pos<=mid) cg(p<<1,l,mid,pos);
else cg(p<<1|1,mid+1,r,pos);
sm[p]=add(sm[p<<1],sm[p<<1|1]);
}
void print(node a){
for(int i=0;i<=63;++i) printf("%llu ",a.a[i]);
printf("\n");
// for(int i=0;i<=63;++i) printf("%d ",a.x[i]);
// printf("\n");
}
int main(){
IO.init();
n = read(), q = read(), read();
for(int i=1;i<=n;++i){
m = read();
for(int j=1;j<=m;++j) s[j] = read(), o[j] = read(), read(A[j]);
read(B);
a[i]=cj();
// print(a[i]);
}
build(1,1,n);
int op,i,l,r;
unsigned long long x;
while(q--){
read(op);
if(op){
i=read();
m=read();
for(int j=1;j<=m;++j) s[j] = read(), o[j] = read(), read(A[j]);
read(B);
a[i]=cj();
cg(1,1,n,i);
}
else{
l=read(),r=read(),read(x);
node ans=ck(1,1,n,l,r);
// print(ans);
unsigned long long as=0;
for(int i=0;i<=63;++i){
bool nw=ans.x[i];
nw^=((__builtin_popcountll(ans.a[i]&x))&1);
if(nw) as|=(1ll<<i);
}
printf("%llu\n",as);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7912kb
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: 0
Accepted
time: 2ms
memory: 9896kb
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:
9487331362121050549 3906661590723083106 15757672015979182109 4975471776251039345 11503109206538591140 3763610618439604410
result:
ok 6 tokens
Test #3:
score: 0
Accepted
time: 12ms
memory: 9948kb
input:
1 20000 400 32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...
output:
11827781865759498816 7454610526276185721 9581050724293785387 2177163806257271094 14004004964877510141 18073834598135159471 16966489063087641088 12289032565388413023 17823140805867698239 18104549908461644670 15570008264282957124 12400954982104000299 9842549278742638708 16535034933613060362 1561642006...
result:
ok 19600 tokens
Test #4:
score: 0
Accepted
time: 1873ms
memory: 12196kb
input:
500 20000 400 32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...
output:
9119093329811149961 16901643057538871933 17161855998497876349 3964234071281411558 13588188063229334268 15557968976322375381 4612345875926431452 9507168112801039022 9504318642653891468 217407202160767706 12982350345598971306 17957502630817476223 6353877977318728572 15552768639781831485 16778108770682...
result:
ok 19600 tokens
Test #5:
score: 0
Accepted
time: 2919ms
memory: 14964kb
input:
4000 20000 400 35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...
output:
11875257514484243925 3443357416933857062 16160011677622853538 1582145987019406393 15019762274690743371 3128972641411454448 10632018957963074870 2420532366876270818 16130728863118353230 15834956073901517645 18404809296474853851 10982435108266120760 16463778300806795274 11990886156320593058 1145171640...
result:
ok 19600 tokens
Test #6:
score: 0
Accepted
time: 4158ms
memory: 55140kb
input:
20000 20000 0 34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...
output:
8031710763259664674 10015579400510819759 9509776159199873854 252965904282343862 17471441301398284397 6167329408972068582 11581702001320217920 13373488743211628824 2094753313448112669 15503010008451014749 384500896248723935 10501371892025480221 8907735695899875922 14479597201387282763 164403466075406...
result:
ok 20000 tokens
Test #7:
score: 0
Accepted
time: 4148ms
memory: 56040kb
input:
20000 20000 20 28 31 1 17220760822712602145 12 1 10079395927654210001 40 0 10440736241216457314 20 1 14759495678166748212 55 1 8734257463550073646 60 0 543206106562221008 29 1 5402811237936853387 52 1 3884345269948184760 22 0 7873959847686200341 15 1 18396630536251250330 25 0 18230407003294263406 14...
output:
6531775129959975384 6212576544894999781 4191848452578359691 2769536540387251859 15526337103142577854 14948743844803225542 15235110724610778185 9004056994453026335 1028305510694260706 13496210650896843548 13961471020487846633 1864980030930734934 15243868808579626755 10451839696548403150 1178402342726...
result:
ok 19980 tokens
Test #8:
score: 0
Accepted
time: 4166ms
memory: 55100kb
input:
20000 20000 400 41 15 1 10590708978689078436 33 0 17448869030270552656 37 1 16782453056389226553 2 1 18313039076194285622 53 1 7894371271572806769 60 1 14563226108042670650 56 0 12694119759311053234 12 1 969626878679760122 28 1 8906626075909573228 20 1 11632670066953088447 50 0 13097960756795495550 ...
output:
7425391644666486729 17533666397961516801 16986235811843827275 1784742314571007240 13192305384063626572 12739810377012216000 1179361465141596122 7698346401428161235 6903188112913915716 5380404381348976227 16126105607866972637 12798978320947566556 11234201442491665890 16073897288956866956 151328474491...
result:
ok 19600 tokens
Test #9:
score: 0
Accepted
time: 4170ms
memory: 56352kb
input:
20000 20000 400 33 39 1 17067623245236507261 27 1 7041428814521205530 50 1 10823426118594256003 28 1 7163716190894912799 12 1 4080987667516350158 63 0 17082717673883070565 17 0 11310350135715835231 51 1 12855244004029414317 38 0 9814237273168847221 57 1 3708701962235763971 37 0 10158992933772396697 ...
output:
6864973236048047224 18318008901523164537 13500746067907696382 13161681605750995854 3452654261090196316 14847903013724109682 7301818645657195470 15784097910646013208 6555334273152043996 6337001136120562705 7065460407919669838 17502323856909932125 12099828260978288865 17244785354672463736 159661862214...
result:
ok 19600 tokens
Test #10:
score: 0
Accepted
time: 630ms
memory: 54648kb
input:
20000 20000 0 37 46 0 4806156443854081866 29 0 6910842714881233745 61 0 9379366064412681113 32 1 718568893402460472 45 0 1234243654449881049 16 0 9791590151480029686 24 1 801156398497308107 20 1 1638149966892153162 3 1 483739892768149714 56 1 3070030763953269690 38 1 11944075913457601606 6 1 8068547...
output:
17693343388614420171 11014279187501816246 7111154205373939902 5948421254644613369 5776121468606637836 16944170640450069348 8394185836099893155 11947149219582604015 4508739183749291929 11471060687727420580 3924131475517252887 1743542114579130111 14487529569441993654 8062193838630657668 18359613799309...
result:
ok 20000 tokens
Test #11:
score: 0
Accepted
time: 721ms
memory: 55084kb
input:
20000 20000 400 31 63 1 14360706182574306953 17 0 4643864577315796645 48 0 11264878137122897405 18 1 14150130986659920202 25 1 15979000250901513596 49 0 16241841209566112679 37 1 16762565151400121253 14 1 7376170230332808198 26 1 10868082441744868454 27 1 6949308347230687639 44 1 4116452321258930556...
output:
4493451016206578040 14208826853413050113 15020158700931574670 16337826900074673926 5403566933376608394 8871156492968482557 8911109963819675601 6213157285507240354 17190717170193641517 15578273901773478953 1369444627312020075 11786462107951385516 17634527799358234224 18347358352139830828 145863906383...
result:
ok 19600 tokens
Test #12:
score: -100
Time Limit Exceeded
input:
20000 20000 0 25 16 0 2668205375195949736 34 0 2748287585311204102 37 1 4531486636255948251 24 0 14410309392802368907 52 1 851885811168352867 47 1 15887239727531457455 42 0 8819527325570258215 44 0 16146066124743535517 46 1 1041563265194349313 11 1 13140073107604291185 0 1 16670532562293262804 56 1 ...
output:
5924012028700061898 4718073419648080016 13993322115865028469 82790239609178342 887419913876033685 15321668567642867070 8962935781265467660 1552533755174937777 16683793257623944188 6900756788022393102 10981237528745871227 5789630421744738481 9056874037200094100 15328577526113324947 627381852022728881...