Submission #1293139

---

Source Code Expand

#include <cstdio> 
#include <cmath>
#include <iostream>
using namespace std;
//1860ms
int N, M;
int L[300010], R[300010];
int l, r;
int l1[100010], r1[100010];
int sq;
double E = 1e-6;
int tree[300000];
int left2[300000], right2[300000];
int m;
int del[100010];

void addTree(int nd, int ll, int rr)
{
	if(ll<=left2[nd] && rr>=right2[nd]){
		tree[nd] ++;
		return ;
	}
	if(ll>right2[nd] || rr<left2[nd])
		return ;
	addTree(2*nd, ll, rr);
	addTree(2*nd+1, ll ,rr);
}


void solve()
{
	int i, j;
	m = 1;
	while(m<M)
		m *= 2;
	for(i=0; i<m; i++){
		left2[m+i] = i+1;
		right2[m+i] = i+1;
	}
	for(i=m-1; i>=1; i--){
		left2[i] = left2[2*i];
		right2[i] = right2[2*i+1];
	}
	
	int n;
	sq = (int)(sqrt(1.0*M)) + 1;
	for(i=0; i<N; i++){
		l = L[i], r = R[i];
		n = 0;
		int rsq = (int)(sqrt(1.0*r)) + 1;
		//for(j=1; j<=r && j<=sq; j++){
		for(j=1; j<=rsq; j++){
			l1[n] = (l-1)/j+1;
			r1[n] = r/j;
			if(l1[n] <= r1[n] && r1[n]>rsq){
				if(l1[n] < rsq+1)
					l1[n] = rsq+1;
				n ++;
			}
		}
		for(j=0; j<n/2; j++){
			swap(l1[j], l1[n-1-j]);
			swap(r1[j], r1[n-1-j]);
		}
		for(j=0; j<n; j++)
			del[j] = 0;
		int now = 0;
		for(j=1; j<n; j++){
			if(l1[j]<=r1[now]){
				r1[now] = r1[j];
				del[j] = 1;
			}
			else{
				now = j;
			}
		}
		for(j=0; j<n; j++){
			if(del[j] == 0)
				addTree(1, l1[j], r1[j]);
		}
		//for(j=1; j<=sq&&j<=r; j++){
		for(j=1; j<=sq&&j<=rsq; j++){
			if(r/j - (l-1)/j > 0)
				tree[m+j-1] ++;
		}
	}
	
	for(i=1; i<=M; i++){
		int sum = 0;
		int nd = m+i-1;
		while(nd>=1){
			sum += tree[nd];
			nd /= 2;
		}
		printf("%d\n", sum);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int i;
	scanf("%d%d", &N, &M);
	for(i=0; i<N; i++)
		scanf("%d%d", &L[i], &R[i]);
	solve();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:103:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:105:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &L[i], &R[i]);
                              ^

Judge Result