QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #37164 | #1279. Distinct Number | wyhao | ML | 1ms | 1732kb | C++ | 1.2kb | 2022-06-30 13:32:23 | 2022-06-30 13:32:26 |
Judging History
answer
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=4000005;
int TT,n,t,s,rt;
bool vis[65];
struct node{
int l,r,flag;
ll sum;
}T[N];int cnt;
ll L,R;
void change(int &p,ll x,ll y){
if(!p){
p=++cnt;
T[p].l=T[p].r=0;
T[p].sum=T[p].flag=0;
}
if(T[p].flag) return;
if(L<=x and y<=R){
T[p].flag=1;
T[p].sum=y-x+1;
return;
}
ll mid=(x+y)>>1;
if(L<=mid) change(T[p].l,x,mid);
if(mid<R) change(T[p].r,mid+1,y);
T[p].sum=T[T[p].l].sum+T[T[p].r].sum;
}
int main(){
ll x,y,l,r;
ll a,b;
scanf("%d",&TT);
while(TT--){
scanf("%d",&n);
scanf("%lld",&x);
y=x;t=0;s=0;rt=0;cnt=0;
while(y){
vis[t]=y&1;
if(y&1) s++;
y>>=1;t++;
}
y=(1<<s)-1;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&l,&r);
if(r-l+1>x){
L=0;R=y;
change(rt,0,y);
continue;
}
a=b=0;
for(int i=t;~i;i--){
if(vis[i]){
a<<=1;
if((l>>i)&1) a++;
b<<=1;
if((r>>i)&1) b++;
}
}
if(a<=b){
L=a;R=b;
change(rt,0,y);
}else{
L=0;R=a;
change(rt,0,y);
L=b;R=y;
change(rt,0,y);
}
}
printf("%lld\n",T[rt].sum);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 1732kb
input:
3 2 1 1 2 343 34345 1 3 1 3 1 123242343 1 1000000000000000000
output:
2 3 32768
result:
ok 3 tokens
Test #2:
score: -100
Memory Limit Exceeded
input:
902 5 35 2 17 19 24 32 55 59 63 73 97 5 55 3 17 35 37 38 39 43 82 87 88 1 37 46 88 4 79 1 9 40 56 56 56 57 78 8 61 5 7 19 21 27 33 34 36 36 38 59 73 77 79 94 97 2 86 0 23 72 78 7 43 5 10 12 21 22 34 36 58 65 71 72 88 91 99 9 74 16 24 31 41 44 48 48 49 51 51 57 57 61 65 69 71 85 93 4 85 5 44 46 47 54...