Submission #101850

---

Source Code Expand

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long i64;

int N, M;
int L[100000], R[100000];
pair<int, int> las[2100000];

void update(int l, int r, int p){ las[l] = min(las[l], make_pair(r, p)); }

int db[1000000][17];
const int INF = 10000000;

int bin(int p)
{
	int ret = 0;
	int cp = p + M;
	for(int i=16;i>=0;i--){
		if(p >= M){
			if(db[p-M][i] == INF) continue;
			if(db[p-M][i] <= cp-M){
				ret += 1<<i;
				p = db[p-M][i]+M;
			}
		}else{
			if(db[p][i] == INF) continue;
			if(db[p][i] <= cp){
				ret += 1<<i;
				p = db[p][i];
			}
		}
	}
	return ret;
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=0;i<N;i++) scanf("%d%d", L+i, R+i);
	for(int i=0;i<=2*M;i++) las[i] = make_pair(10000000, -1);

	for(int i=0;i<N;i++){
		if(L[i] < R[i]){
			update(L[i], R[i], i);
			update(L[i]+M, R[i]+M, i);
		}else{
			update(L[i], R[i]+M, i);
			//update(L[i]+M, R[i]+2*M, i);
		}
	}
	for(int i=2*M-1;i>=0;i--) las[i] = min(las[i], las[i+1]);

	//まだまだ負けないんだから～＞＜
	for(int i=0;i<17;i++){
		for(int j=0;j<M;j++){
			if(i==0) db[j][i] = las[j].first;
			else{
				int nex = db[j][i-1]; //2^(i-1) した
				if(nex == INF){
					db[j][i] = INF;
					continue;
				}else{
					if(nex >= M){
						db[j][i] = db[db[j][i-1]-M][i-1] + M;
					}else{
						db[j][i] = db[db[j][i-1]][i-1];
					}
					if(db[j][i] > j + M) db[j][i] = INF;
				}
			}
		}
	}

	int ret = 0;
	for(int i=0;i<M;i++) ret = max(ret, bin(i));

	printf("%d\n", ret);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result