# Japan Alumni Group Summer Camp 2013 Warming Up

## Submission #813937

### 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=200000;
int nxt[nmax][20];

int main(void){
cin >> n >> m;
rep(i,n){
int s,t;
cin >> s >> t;
if(s>t) t+=m;
ary.push_back(state(t,s));
ary.push_back(state(t+m,s+m));
}

sort(_all(ary));

int cur=0,tar=0;
const int all=2*n;
while(cur<all){
while(tar<all && ary[tar].second<ary[cur].first) tar++;
nxt[cur++][0]=tar;
}

rep(k,19)rep(i,2*n){
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 s=ary[i].second,cur=i,num=0;
rrep(k,20){
int tar=nxt[cur][k];
if(tar!=all && ary[tar].first<=s+m){
cur=tar;
num|=1<<k;
}
}
chmax(ans,num+1);
}

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

### Submission

Task問題 A - Anime Master Hec 2016/07/22 05:43:59 +0000 C++11 (GCC 4.8.1) AC 100 1762 Byte 265 ms 18136 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 35 ms 816 KB 10 AC 27 ms 924 KB 11 AC 26 ms 800 KB 12 AC 28 ms 968 KB 13 AC 28 ms 876 KB 14 AC 27 ms 872 KB 15 AC 28 ms 920 KB 16 AC 25 ms 872 KB 17 AC 26 ms 876 KB 18 AC 26 ms 872 KB 19 AC 27 ms 876 KB 2 AC 26 ms 876 KB 20 AC 27 ms 928 KB 21 AC 27 ms 804 KB 22 AC 26 ms 876 KB 23 AC 26 ms 924 KB 24 AC 25 ms 876 KB 25 AC 26 ms 880 KB 26 AC 25 ms 880 KB 27 AC 27 ms 872 KB 28 AC 25 ms 804 KB 29 AC 26 ms 880 KB 3 AC 24 ms 928 KB 30 AC 26 ms 856 KB 31 AC 26 ms 916 KB 32 AC 27 ms 876 KB 33 AC 26 ms 872 KB 34 AC 24 ms 876 KB 35 AC 27 ms 924 KB 36 AC 26 ms 876 KB 37 AC 25 ms 868 KB 38 AC 26 ms 920 KB 39 AC 26 ms 924 KB 4 AC 26 ms 928 KB 40 AC 26 ms 872 KB 41 AC 27 ms 928 KB 42 AC 27 ms 876 KB 43 AC 26 ms 876 KB 44 AC 26 ms 868 KB 45 AC 26 ms 804 KB 46 AC 27 ms 876 KB 47 AC 27 ms 840 KB 48 AC 29 ms 928 KB 49 AC 28 ms 868 KB 5 AC 27 ms 924 KB 50 AC 28 ms 876 KB 51 AC 25 ms 872 KB 52 AC 28 ms 864 KB 53 AC 27 ms 832 KB 54 AC 26 ms 848 KB 55 AC 26 ms 868 KB 56 AC 26 ms 836 KB 57 AC 28 ms 872 KB 58 AC 233 ms 18136 KB 59 AC 231 ms 18136 KB 6 AC 27 ms 924 KB 60 AC 223 ms 18104 KB 61 AC 238 ms 18136 KB 62 AC 238 ms 18136 KB 63 AC 236 ms 18132 KB 64 AC 265 ms 18136 KB 65 AC 83 ms 5720 KB 66 AC 133 ms 9952 KB 67 AC 86 ms 5992 KB 68 AC 35 ms 1768 KB 69 AC 30 ms 1048 KB 7 AC 27 ms 812 KB 70 AC 34 ms 1516 KB 71 AC 28 ms 924 KB 72 AC 29 ms 916 KB 73 AC 30 ms 1048 KB 74 AC 32 ms 1252 KB 75 AC 36 ms 1648 KB 76 AC 42 ms 2288 KB 77 AC 35 ms 1636 KB 78 AC 40 ms 2156 KB 79 AC 31 ms 1256 KB 8 AC 26 ms 928 KB 80 AC 31 ms 1176 KB 81 AC 37 ms 2032 KB 82 AC 34 ms 1860 KB 83 AC 34 ms 1564 KB 84 AC 43 ms 2660 KB 85 AC 44 ms 2532 KB 86 AC 33 ms 1508 KB 87 AC 37 ms 1892 KB 88 AC 33 ms 1896 KB 89 AC 45 ms 2672 KB 9 AC 27 ms 872 KB