Submission #58999

---

Source Code Expand

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<ctype.h>
#include<iostream>
#include<iomanip>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<complex>
#define EPS (1e-10)
#define PI (3.141592653589793238)
#define MP make_pair
typedef long long ll;
using namespace std;

int n,Q;
int s[500000];
int t[500000];
pair<int,int> ps[500000];
int next[25][210000];

int ans[500000];

int main(void){

	scanf("%d %d",&n,&Q);
	for(int i=0;i<n;i++){
		scanf("%d %d",&s[i],&t[i]);
	}

	for(int i=0;i<n;i++){
		ps[i]=MP(t[i],i);
		ps[n+i]=MP(s[i],n+i);
	}
	sort(&ps[0],&ps[2*n]);

	int last=-1;
	for(int i=2*n-1;i>=0;i--){
		int id=ps[i].second;
		if(id<n){
			next[0][id]=last;
		}else{
			id-=n;
			if(last<0 || t[last]>t[id]){
				last=id;
			}
		}
	}

	for(int k=0;k<20;k++){
		for(int i=0;i<n;i++){
			if(next[k][i]<0)next[k+1][i]=-1;
			else next[k+1][i]=next[k][next[k][i]];
		}
	}

	/*for(int k=0;k<20;k++){
		printf("[%d]\n",k);
		for(int i=0;i<n;i++){
			printf("%2d ",next[k][i]);
		}
		printf("\n");
	}*/

	//return 0;

	vector<pair<pair<int,int>,int> > qu;
	for(int q=0;q<Q;q++){
		int qs,qt;
		scanf("%d %d",&qs,&qt);

		qu.push_back(MP(MP(qs,qt),q));
	}
	sort(qu.begin(),qu.end());

	vector<pair<int,int> > range;
	for(int i=0;i<n;i++){
		range.push_back(MP(t[i],i));
	}
	sort(range.begin(),range.end());

	int now=0;
	for(int q=0;q<Q;q++){
		int qs=qu[q].first.first;
		int qt=qu[q].first.second;
		int qpos=qu[q].second;

		while(now<n && s[range[now].second]<qs){
			now++;
		}
		if(now>=n){
			ans[qpos]=0;
			continue;
		}
		if(qt<t[range[now].second]){
			ans[qpos]=0;
			continue;
		}

		int i=range[now].second;
		int tmp=0,j=i;
		for(int k=19;k>=0;k--){
			int j2=next[k][j];
			if(j2>=0 && t[j2]<=qt){
				j=j2;
				tmp|=(1<<k);
			}
		}

		ans[qpos]=tmp+1;
	}

	for(int i=0;i<Q;i++){
		printf("%d\n",ans[i]);
	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:37:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:79:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result