Submission #3054264

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ind;
struct node{
	int ls,rs,sum;
}tr[20500010];
void pushup(int o){
	tr[o].sum=tr[tr[o].ls].sum+tr[tr[o].rs].sum;
}
void build(int &o,int l,int r){
	o=++ind;
	if(r==l)return;
	build(tr[o].ls,l,(l+r)/2);
	build(tr[o].rs,(l+r)/2+1,r);
}
void update(int &_new,int old,int l,int r,int pos){
	_new=++ind;
	tr[_new]=tr[old];
	tr[_new].sum++;
	if(l==r)return;
	int mid=(l+r)/2;
	if(pos<=mid)update(tr[_new].ls,tr[old].ls,l,mid,pos);
	else update(tr[_new].rs,tr[old].rs,mid+1,r,pos);
	pushup(_new);
}
int query(int _new,int old,int l,int r,int x,int y){
	if(x>r||y<l)return 0;
	if(x<=l&&y>=r)return tr[_new].sum-tr[old].sum;
	int mid=(l+r)/2;
	if(y<=mid)return query(tr[_new].ls,tr[old].ls,l,mid,x,y);
	else if(x>mid)return query(tr[_new].rs,tr[old].rs,mid+1,r,x,y);
	else return query(tr[_new].ls,tr[old].ls,l,mid,x,mid)+query(tr[_new].rs,tr[old].rs,mid+1,r,mid+1,y);
}
int rt[551000];
struct data{
	int l,r;
	friend bool operator <(data a,data b){
		return a.l==b.l?a.r<b.r:a.l<b.l;
	}
}item[300100];
void solve(int d){
	int res=0,now=0,pre=0;
	for(int i=1;i*d<=m;++i){
		int k=0;
		for(int j=16;j>=0;--j){
			if((1<<j)>n)continue;
			if((k+(1<<j))<=n&&(item[k+(1<<j)].l-1)/d<i)k+=(1<<j);
		}
		now=k;
		if(now>n)now=n;
		int t=(item[now].l-1)/d;
		res+=query(rt[now],rt[pre],1,m,d*(t+1),m);
		pre=now;
	}
	printf("%d\n",res);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&item[i].l,&item[i].r);
	}
	sort(item+1,item+n+1);
	build(rt[0],1,n);
	for(int i=1;i<=n;++i){
		update(rt[i],rt[i-1],1,m,item[i].r);
	}
	for(int d=1;d<=m;++d){
		solve(d);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:63:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&item[i].l,&item[i].r);
                                      ^

Judge Result