QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#867028#9727. Barkley IIImeisgoodTL 348ms77664kbC++206.3kb2025-01-23 00:42:232025-01-23 00:42:23

Judging History

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

  • [2025-01-23 00:42:23]
  • 评测
  • 测评结果：TL
  • 用时：348ms
  • 内存：77664kb
查看
  • [2025-01-23 00:42:23]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize(" unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll tests, n, m, a[MAXN], op, aa, bb, cc, ans, pw[63];
struct Node{
  int pos[63], l, r;
  ll sum;
}tmp, mem;
Node Merge(Node x, Node y){
  mem.l=x.l;
  mem.r=y.r;
  mem.sum=x.sum|y.sum;
  for(ll i=0; i<63; i++){
    if(x.pos[i]==-1||y.pos[i]==-1||(x.pos[i]&&y.pos[i])){
      mem.pos[i]=-1;
    }
    else if(x.pos[i]&&!y.pos[i]){
      mem.pos[i]=x.pos[i];
    }
    else if(!x.pos[i]&&y.pos[i]){
      mem.pos[i]=y.pos[i];
    }
    else{
      mem.pos[i]=0;
    }
  }
  return mem;
}
struct SegTree{
  Node tr[4*MAXN];
  void Pushup(ll x){
    tr[x]=Merge(tr[x*2], tr[x*2+1]);
  }
  void Build(ll l, ll r, ll x){
    tr[x].l=l;
    tr[x].r=r;
    if(tr[x].l==tr[x].r){
      tr[x].sum=a[tr[x].l];
      for(ll i=0; i<63; i++){
        tr[x].pos[i]=((tr[x].sum&pw[i])==0)?tr[x].l:0;
      }
      return;
    }
    ll mid=(l+r)/2;
    Build(l, mid, x*2);
    Build(mid+1, r, x*2+1);
    Pushup(x);
  }
  void Update_Range(ll l, ll r, ll v, ll x){
    if(tr[x].l==tr[x].r){
      tr[x].sum&=v;
      for(ll i=0; i<63; i++){
        tr[x].pos[i]=((tr[x].sum&pw[i])==0)?tr[x].l:0;
      }
      return;
    }
    if(tr[x*2].r>=l&&(tr[x*2].sum&(~v))){
      Update_Range(l, r, v, x*2);
    }
    if(tr[x*2+1].l<=r&&(tr[x*2+1].sum&(~v))){
      Update_Range(l, r, v, x*2+1);
    }
    Pushup(x);
  }
  void Update_Point(ll pos, ll v, ll x){
    if(tr[x].l==tr[x].r){
      tr[x].sum=v;
      for(ll i=0; i<63; i++){
        tr[x].pos[i]=((tr[x].sum&pw[i])==0)?tr[x].l:0;
      }
      return;
    }
    if(tr[x*2].r>=pos){
      Update_Point(pos, v, x*2);
    }
    else{
      Update_Point(pos, v, x*2+1);
    }
    Pushup(x);
  }
  Node Query(ll l, ll r, ll x){
    if(tr[x].l>=l&&tr[x].r<=r){
      return tr[x];
    }
    Node ret;
    ret.sum=ret.l=ret.r=0;
    for(ll i=0; i<63; i++){
      ret.pos[i]=0;
    }
    if(tr[x*2].r>=l){
      ret=Merge(ret, Query(l, r, x*2));
    }
    if(tr[x*2+1].l<=r){
      ret=Merge(ret, Query(l, r, x*2+1));
    }
    return ret;
  }
}t;
namespace FAST_IO{
	const int LEN=1<<20;
	char BUF[LEN],PUF[LEN];
	int Pin=LEN,Pout;
	inline void flushin(){memcpy(BUF,BUF+Pin,LEN-Pin),fread(BUF+LEN-Pin,1,Pin,stdin),Pin=0;return;}
	inline void flushout(){fwrite(PUF,1,Pout,stdout),Pout=0;return;}
	inline char Getc(){return (Pin==LEN?(fread(BUF,1,LEN,stdin),Pin=0):0),BUF[Pin++];}
	inline char Get(){return BUF[Pin++];}
	inline void Putc(char x){if(Pout==LEN)flushout(),Pout=0;PUF[Pout++]=x;}
	inline void Put(char x){PUF[Pout++]=x;}
	template<typename tp=ll>inline tp read(){(Pin+32>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;return res*f;}
	template<typename tp>inline void write(tp a,char b='\n'){
		static int stk[20],top;
		(Pout+32>=LEN)?flushout():void();
		if(a<0)Put('-'),a=-a;
		else if(a==0)Put('0');
		for(top=0;a;a/=10)stk[++top]=a%10;
		for(;top;--top)Put(stk[top]^48);
		Put(b);
	}
}
using namespace FAST_IO;
int main(){
  pw[0]=1;
  for(ll i=1; i<63; i++){
    pw[i]=pw[i-1]*2;
  }
  n=read();
  m=read();
  for(ll i=1; i<=n; i++){
    a[i]=read();
  }
  t.Build(1, n, 1);
  while(m--){
    op=read();
    if(op==1){
      aa=read();
      bb=read();
      cc=read();
      t.Update_Range(aa, bb, cc, 1);
    }
    else if(op==2){
      aa=read();
      bb=read();
      t.Update_Point(aa, bb, 1);
    }
    else{
      aa=read();
      bb=read();
      tmp=t.Query(aa, bb, 1);
      ans=0;
      cc=-1;
      for(ll i=62; i>=0; i--){
        if(tmp.pos[i]==0){
          ans+=pw[i];
          continue;
        }
        if(tmp.pos[i]!=0&&tmp.pos[i]!=-1&&(cc==-1||cc==tmp.pos[i])){
          cc=tmp.pos[i];
          ans+=pw[i];
        }
      }
      write(ans);
    }
  }
  flushout();
	return 0 ;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7884kb

input:

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2

output:

7
6
7
3
3
8

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 7716kb

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: 1ms
memory: 7888kb

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: 2ms
memory: 7920kb

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: 348ms
memory: 77664kb

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:

result:
English 繁體中文 简体中文

Server Time: 2025-02-01 17:57:39 | OpenSource Project