Submission #813931


Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

int n,m;

using state=pair<int,int>;
vector<state> ary;

const int nmax=200000;

int s[nmax],t[nmax];
int nxt[nmax][20];

int main(void){
	cin >> n >> m;
	rep(i,n){
		cin >> s[i] >> t[i];
		if(s[i]>t[i]) t[i]+=m;
		s[n+i]=s[i]+m;
		t[n+i]=t[i]+m;
	}

	const int all=2*n;
	rep(i,all){
		ary.push_back(state(t[i],i));
		ary.push_back(state(s[i],all+i));
	}

	sort(_all(ary));

	int last=all;

	rrep(i,2*all){
		int id=ary[i].second;
		if(id<all){
			nxt[id][0]=last;
		}else{
			id-=all;
			if(last==all || t[last]>t[id]) last=id;
		}
	}

	rep(k,20)rep(i,all){
		if(nxt[i][k]==all)
			nxt[i][k+1]=all;
		else
			nxt[i][k+1]=nxt[nxt[i][k]][k];
	}

	int ans=0;

	rep(i,n){
		int cur=i,num=0;
		rrep(k,20){
			int tar=nxt[cur][k];
			if(tar!=all && t[tar]<=s[i]+m){
				cur=tar;
				num|=1<<k;
			}
		}
		chmax(ans,num+1);
	}

	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task A - Anime Master
User Hec
Language C++11 (GCC 4.8.1)
Score 0
Code Size 1861 Byte
Status WA
Exec Time 327 ms
Memory 21408 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 56
WA × 33
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 5, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 6, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 7, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9
Case Name Status Exec Time Memory
1 AC 30 ms 932 KB
10 AC 28 ms 944 KB
11 AC 35 ms 940 KB
12 AC 28 ms 944 KB
13 AC 27 ms 948 KB
14 AC 27 ms 1052 KB
15 AC 28 ms 948 KB
16 WA 27 ms 940 KB
17 WA 27 ms 1048 KB
18 AC 27 ms 1052 KB
19 AC 25 ms 920 KB
2 AC 26 ms 1048 KB
20 WA 27 ms 1052 KB
21 AC 27 ms 944 KB
22 AC 24 ms 948 KB
23 AC 25 ms 864 KB
24 AC 26 ms 1052 KB
25 AC 26 ms 1052 KB
26 AC 24 ms 1052 KB
27 AC 26 ms 1044 KB
28 AC 24 ms 972 KB
29 AC 26 ms 1056 KB
3 AC 25 ms 1048 KB
30 AC 26 ms 948 KB
31 WA 28 ms 920 KB
32 AC 24 ms 1048 KB
33 AC 26 ms 948 KB
34 AC 27 ms 948 KB
35 AC 26 ms 1048 KB
36 AC 30 ms 1040 KB
37 AC 26 ms 944 KB
38 WA 26 ms 1048 KB
39 AC 24 ms 948 KB
4 AC 26 ms 944 KB
40 AC 27 ms 948 KB
41 WA 26 ms 1048 KB
42 AC 26 ms 948 KB
43 WA 26 ms 944 KB
44 AC 26 ms 1048 KB
45 WA 27 ms 944 KB
46 AC 26 ms 1052 KB
47 WA 27 ms 944 KB
48 AC 26 ms 1048 KB
49 AC 26 ms 1048 KB
5 AC 24 ms 1044 KB
50 AC 26 ms 1052 KB
51 WA 26 ms 1048 KB
52 AC 26 ms 1056 KB
53 AC 27 ms 1052 KB
54 AC 26 ms 1048 KB
55 WA 26 ms 928 KB
56 AC 26 ms 948 KB
57 AC 26 ms 1052 KB
58 AC 254 ms 21400 KB
59 WA 227 ms 21308 KB
6 AC 27 ms 940 KB
60 AC 259 ms 21408 KB
61 WA 280 ms 21320 KB
62 WA 286 ms 21344 KB
63 WA 296 ms 21308 KB
64 WA 327 ms 21392 KB
65 AC 99 ms 6696 KB
66 AC 164 ms 11712 KB
67 WA 104 ms 7076 KB
68 AC 38 ms 2096 KB
69 AC 28 ms 1112 KB
7 WA 24 ms 1048 KB
70 AC 33 ms 1712 KB
71 WA 26 ms 1044 KB
72 AC 27 ms 1184 KB
73 AC 25 ms 1068 KB
74 AC 31 ms 1460 KB
75 WA 36 ms 1968 KB
76 AC 42 ms 2604 KB
77 AC 37 ms 1968 KB
78 WA 44 ms 2532 KB
79 WA 32 ms 1456 KB
8 WA 26 ms 948 KB
80 WA 27 ms 1440 KB
81 WA 40 ms 2352 KB
82 WA 38 ms 2008 KB
83 WA 35 ms 1872 KB
84 WA 49 ms 2984 KB
85 WA 47 ms 2856 KB
86 WA 35 ms 1840 KB
87 WA 37 ms 2096 KB
88 WA 41 ms 2136 KB
89 WA 52 ms 3112 KB
9 AC 26 ms 1048 KB