# Japan Alumni Group Summer Camp 2013 Warming Up

## Submission #813936

### Source codeソースコード

```#include <bits/stdc++.h>

#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)

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

#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=200010;

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,19)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

Task問題 A - Anime Master 074_Hec 2016/07/22 05:42:57 +0000 C++11 (GCC 4.8.1) AC 100 1861 Byte 334 ms 21304 KB

### Test case

#### Set

Set name Score得点 / Max score Cases
All 100 / 100 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

#### Test case

 Case name Status状態 Exec time実行時間 Memory usageメモリ使用量 1 AC 37 ms 816 KB 10 AC 24 ms 928 KB 11 AC 26 ms 932 KB 12 AC 26 ms 928 KB 13 AC 26 ms 876 KB 14 AC 24 ms 880 KB 15 AC 26 ms 876 KB 16 AC 27 ms 872 KB 17 AC 26 ms 872 KB 18 AC 26 ms 924 KB 19 AC 24 ms 928 KB 2 AC 26 ms 924 KB 20 AC 26 ms 932 KB 21 AC 24 ms 924 KB 22 AC 24 ms 924 KB 23 AC 24 ms 876 KB 24 AC 27 ms 880 KB 25 AC 26 ms 808 KB 26 AC 27 ms 872 KB 27 AC 25 ms 924 KB 28 AC 25 ms 928 KB 29 AC 25 ms 884 KB 3 AC 26 ms 924 KB 30 AC 26 ms 872 KB 31 AC 26 ms 928 KB 32 AC 27 ms 884 KB 33 AC 27 ms 884 KB 34 AC 28 ms 924 KB 35 AC 26 ms 876 KB 36 AC 26 ms 876 KB 37 AC 26 ms 924 KB 38 AC 26 ms 924 KB 39 AC 26 ms 928 KB 4 AC 26 ms 920 KB 40 AC 26 ms 928 KB 41 AC 30 ms 924 KB 42 AC 28 ms 924 KB 43 AC 27 ms 884 KB 44 AC 26 ms 876 KB 45 AC 25 ms 808 KB 46 AC 26 ms 876 KB 47 AC 26 ms 928 KB 48 AC 26 ms 876 KB 49 AC 26 ms 928 KB 5 AC 26 ms 932 KB 50 AC 24 ms 928 KB 51 AC 26 ms 928 KB 52 AC 26 ms 932 KB 53 AC 26 ms 924 KB 54 AC 26 ms 868 KB 55 AC 26 ms 968 KB 56 AC 26 ms 928 KB 57 AC 26 ms 928 KB 58 AC 252 ms 21216 KB 59 AC 235 ms 21208 KB 6 AC 27 ms 924 KB 60 AC 268 ms 21304 KB 61 AC 287 ms 21216 KB 62 AC 291 ms 21212 KB 63 AC 302 ms 21212 KB 64 AC 334 ms 21208 KB 65 AC 101 ms 6620 KB 66 AC 166 ms 11608 KB 67 AC 106 ms 7004 KB 68 AC 36 ms 2028 KB 69 AC 28 ms 1000 KB 7 AC 26 ms 876 KB 70 AC 33 ms 1644 KB 71 AC 27 ms 880 KB 72 AC 27 ms 984 KB 73 AC 27 ms 1096 KB 74 AC 30 ms 1380 KB 75 AC 35 ms 1896 KB 76 AC 43 ms 2516 KB 77 AC 36 ms 1856 KB 78 AC 43 ms 2404 KB 79 AC 32 ms 1380 KB 8 AC 28 ms 872 KB 80 AC 29 ms 1188 KB 81 AC 41 ms 2148 KB 82 AC 39 ms 2032 KB 83 AC 34 ms 1744 KB 84 AC 49 ms 2912 KB 85 AC 48 ms 2784 KB 86 AC 35 ms 1776 KB 87 AC 39 ms 2024 KB 88 AC 37 ms 2028 KB 89 AC 50 ms 3048 KB 9 AC 26 ms 924 KB