QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-06-30 13:32:26]
评测

测评结果：ML
用时：1ms
内存：1732kb

查看

[2022-06-30 13:32:23]
提交

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;
}

源文件, 语言: C++

详细

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: