QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#747965	#9727. Barkley III	yylx	TL	204ms	255356kb	C++14	3.4kb	2024-11-14 18:52:54	2024-11-14 18:52:54

Judging History

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

[2025-01-13 03:55:43]
hack成功，自动添加数据
(/hack/1447)

[2024-11-14 18:52:54]
评测

测评结果：TL
用时：204ms
内存：255356kb

查看

[2024-11-14 18:52:54]
提交

answer


#include <bits/stdc++.h>

using namespace std;

long long MAX=9223372036854775807;
//long long MAX=15;

long long n,q,x,y,z,w,as[2000001];
pair<long long,long long> re;

struct tree
{
    int l,r;
    long long x,sum,lt=-1;
};
tree tr[8000001];

void build_tree(int cl,int cr,int ind)
{
    tr[ind].l=cl;
    tr[ind].r=cr;
    if(cl==cr)
    {
        tr[ind].sum=as[cl];
        tr[ind].x=~as[cl];
        return;
    }
    int m=cl+cr>>1;
    build_tree(cl,m,ind<<1);
    build_tree(m+1,cr,(ind<<1)+1);
    tr[ind].sum=tr[ind<<1].sum&tr[(ind<<1)+1].sum;
    tr[ind].x=(tr[ind<<1].sum&tr[(ind<<1)+1].x)|(tr[ind<<1].x&tr[(ind<<1)+1].sum);
}

void envalue(int ind,long long v)
{
    if(tr[ind].lt==-1) tr[ind].lt=v;
    else tr[ind].lt&=v;
    tr[ind].sum&=v;
    if(tr[ind].l==tr[ind].r)
    {
        tr[ind].x=~tr[ind].sum;
        return;
    }
    tr[ind].x&=v;
    return;
}

void push_down(int ind)
{
    if(tr[ind].lt==-1) return;
    envalue(ind<<1,tr[ind].lt);
    envalue((ind<<1)+1,tr[ind].lt);
    tr[ind].lt=-1;
    return;
}

void add(int cl,int cr,int al,int ar,int ind,long long v)
{
    if(cl>=al && cr<=ar)
    {
        envalue(ind,v);
        return;
    }
    push_down(ind);
    int m=cl+cr>>1;
    if(m>=al) add(cl,m,al,ar,ind<<1,v);
    if(m<ar) add(m+1,cr,al,ar,(ind<<1)+1,v);
    tr[ind].sum=tr[ind<<1].sum&tr[(ind<<1)+1].sum;
    tr[ind].x=(tr[ind<<1].sum&tr[(ind<<1)+1].x)|(tr[ind<<1].x&tr[(ind<<1)+1].sum);
    return;
}

pair<long long,long long> findx(int cl,int cr,int al,int ar,int ind)
{
    int m=cl+cr>>1;
    if(cl>=al && cr<=ar) return make_pair(tr[ind].sum,tr[ind].x);
    push_down(ind);
    long long s1=MAX,s2=MAX,x1=0,x2=0;
    if(m>=al) {re=findx(cl,m,al,ar,ind<<1);s1=re.first;x1=re.second;}
    if(m<ar) {re=findx(m+1,cr,al,ar,(ind<<1)+1);s2=re.first;x2=re.second;}
    return make_pair(s1&s2,(s1&x2)|(s2&x1));
}

void modify(int cl,int cr,int p,int ind,long long v)
{
    if(cl==cr)
    {
        tr[ind].sum=v;
        tr[ind].x=~v;
        return;
    }
    push_down(ind);
    int m=cl+cr>>1;
    if(m>=p) modify(cl,m,p,ind<<1,v);
    else modify(m+1,cr,p,(ind<<1)+1,v);
    tr[ind].sum=tr[ind<<1].sum&tr[(ind<<1)+1].sum;
    tr[ind].x=(tr[ind<<1].sum&tr[(ind<<1)+1].x)|(tr[ind<<1].x&tr[(ind<<1)+1].sum);
}

long long locate(int cl,int cr,int al,int ar,int ind,long long v)
{
    int m=cl+cr>>1;
    if(cl>=al && cr<=ar)
    {
        if((tr[ind].x&v)<=(v>>1)) return -1;
        else
        {
            if(cl==cr) return tr[ind].sum;
            else return max(locate(cl,m,al,ar,ind<<1,v),locate(m+1,cr,al,ar,(ind<<1)+1,v));
        }
    }
    push_down(ind);
    long long l1=-1,l2=-1;
    if(m>=al) l1=locate(cl,m,al,ar,ind<<1,v);
    if(m<ar) l2=locate(m+1,cr,al,ar,(ind<<1)+1,v);
    return max(l1,l2);
}

int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i+=1) cin>>as[i];
    build_tree(1,n,1);
    for(int i=1;i<=q;i+=1)
    {
        cin>>x;
        if(x==1)
        {
            cin>>y>>z>>w;
            add(1,n,y,z,1,w);
        }
        if(x==2)
        {
            cin>>y>>z;
            modify(1,n,y,1,z);
        }
        if(x==3)
        {
            cin>>y>>z;
            re=findx(1,n,y,z,1);
            w=locate(1,n,y,z,1,re.second);
            if(w==-1) cout<<re.first<<endl;
            else cout<<(re.first+(re.second&(~w)))<<endl;
        }
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 8ms

memory: 253572kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 12ms

memory: 253620kb

input:

10 10
6760061359215711796 1568091718842717482 1568091718842717482 1568091718842717482 5232472783634052627 8795942500783873690 1568091718842717482 1568091718842717482 1568091718842717482 1568091718842717482
1 3 5 7587422031989082829
3 6 10
1 7 8 5197616143400216932
2 4 2518604563805514908
2 2 4533959...

output:

1568091718842717482
35184908959744
176025477579040
8795942500783873690

result:

ok 4 lines

Test #3:

score: 0

Accepted

time: 12ms

memory: 253644kb

input:

100 100
4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 625967318191814868 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072...

output:

576531121047601152
1
576460752303423488
4263579105072360993
1306043896232411137
4263579105072360993
576531121047601152
633397148123136
0
1153488865559840256
1152922054496880128
1730020640668059136
3533641810948498945
67108864
1730020640668059136
0
633397148123136
1729382296723653632
0
17300206406680...

result:

ok 78 lines

Test #4:

score: 0

Accepted

time: 27ms

memory: 255356kb

input:

1000 1000
3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3639580211161047627 3368486440884437410 3368486440884437410 3368486440...

output:

3368486440884437410
3368486440884437410
3368486440884437410
2251799981457408
0
0
3368486440884437410
0
3326828075601101216
592509842556584322
0
0
0
0
0
0
37154696925806592
0
0
0
3368486440884437410
0
0
3368486440884437410
0
578998425140330496
0
0
134217728
0
3368486440884437410
2306405959167115264
0...

result:

ok 732 lines

Test #5:

score: 0

Accepted

time: 204ms

memory: 254352kb

input:

100000 100000
4364025563773184234 7745126251050571359 5111681002836044963 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7222555899134537718 7745126251050571359 686495...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4613942216556019776
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 75105 lines

Test #6:

score: -100

Time Limit Exceeded

input:

1000000 1000000
5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8796093022208
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
576460754450907136
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...