QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#37152	#1279. Distinct Number	wyhao	ML	1ms	2008kb	C++	1.2kb	2022-06-30 13:24:30	2022-06-30 13:24:32

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:24:32]
评测

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

查看

[2022-06-30 13:24:30]
提交

answer

#include<cstdio>
using namespace std;
typedef long long ll;
const int N=7000005;
int TT,n,t,s,rt;
bool vis[65];
struct node{
	int l,r,flag;
	ll sum;
}T[N];int cnt;
void change(int &p,ll x,ll y,ll l,ll r){
	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,l,r);
	if(mid<r) change(T[p].r,mid+1,y,l,r);
	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;
//		printf("%lld\n",y);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld",&l,&r);
			if(r-l+1>x){
//				printf("0 %d\n",y);
				change(rt,0,y,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++;
				}
			}
//			printf("%lld %lld\n",a,b);
			if(a<=b) change(rt,0,y,a,b);
			else change(rt,0,y,0,a),change(rt,0,y,b,y);
		}
		printf("%lld\n",T[rt].sum);
	}
	return 0;
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 2008kb

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: