Submission #638855


Source Code Expand

#include<iostream>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>

#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

int main(){
  int n,m;
  P2 a[200100];
  int to[100100];

  cin >> n >> m;
  rep(i,n){
    cin >> a[i].fs.sc >> a[i].fs.fs, to[i] = i;
    if(a[i].fs.fs < a[i].fs.sc)a[i].fs.fs += m;
    a[i].sc  = i;
    a[i+n] = a[i];
    a[i+n].fs.fs += m; a[i+n].fs.sc += m;
  }

  sort(a,a+2*n);

  int pos = 1;
  rep(i,n){
    while(pos<i+n && a[pos].fs.sc < a[i].fs.fs)pos++;
    if(pos<i+n && a[pos].fs.fs-m <= a[i].fs.sc){
      to[a[i].sc] = a[pos].sc;
    }
  }

  int ans = 1;
  int d[100100];
  int vis[100100];
  memset(vis,0,sizeof(vis));
  memset(d,0,sizeof(d));

  rep(i,n){
    if(!vis[i]){
      int now = i;
      vis[now] = i+1;
      d[now] = 1;

      while(!vis[to[now]]){
	vis[to[now]] = i+1;
	d[to[now]] = d[now] + 1;
	now = to[now];
      }
      if(vis[now] == vis[to[now]])ans = max(ans,d[now]-d[to[now]]+1);
    }
  }
  cout << ans << endl;
}


  

Submission Info

Submission Time
Task A - Anime Master
User Darsein
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1155 Byte
Status AC
Exec Time 191 ms
Memory 4264 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 89
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 3876 KB
10 AC 31 ms 3880 KB
11 AC 31 ms 3872 KB
12 AC 28 ms 3876 KB
13 AC 30 ms 3872 KB
14 AC 30 ms 3876 KB
15 AC 32 ms 3872 KB
16 AC 34 ms 3872 KB
17 AC 30 ms 3876 KB
18 AC 30 ms 3872 KB
19 AC 30 ms 3872 KB
2 AC 31 ms 3872 KB
20 AC 29 ms 3868 KB
21 AC 31 ms 3872 KB
22 AC 28 ms 3864 KB
23 AC 30 ms 3876 KB
24 AC 30 ms 3876 KB
25 AC 32 ms 3868 KB
26 AC 33 ms 3820 KB
27 AC 30 ms 3872 KB
28 AC 31 ms 3880 KB
29 AC 29 ms 3876 KB
3 AC 29 ms 3880 KB
30 AC 31 ms 3876 KB
31 AC 31 ms 4004 KB
32 AC 29 ms 3872 KB
33 AC 30 ms 3872 KB
34 AC 30 ms 3876 KB
35 AC 30 ms 3880 KB
36 AC 30 ms 3864 KB
37 AC 29 ms 3876 KB
38 AC 31 ms 3876 KB
39 AC 31 ms 3868 KB
4 AC 30 ms 3868 KB
40 AC 31 ms 3872 KB
41 AC 31 ms 3884 KB
42 AC 31 ms 3864 KB
43 AC 29 ms 3872 KB
44 AC 31 ms 3876 KB
45 AC 31 ms 3880 KB
46 AC 31 ms 3872 KB
47 AC 31 ms 3880 KB
48 AC 29 ms 3868 KB
49 AC 30 ms 3876 KB
5 AC 30 ms 3876 KB
50 AC 31 ms 3864 KB
51 AC 29 ms 3876 KB
52 AC 29 ms 3876 KB
53 AC 29 ms 3876 KB
54 AC 29 ms 3872 KB
55 AC 28 ms 3872 KB
56 AC 31 ms 3812 KB
57 AC 29 ms 3876 KB
58 AC 155 ms 4260 KB
59 AC 146 ms 4260 KB
6 AC 30 ms 3876 KB
60 AC 158 ms 4260 KB
61 AC 180 ms 4260 KB
62 AC 191 ms 4264 KB
63 AC 178 ms 4260 KB
64 AC 178 ms 4256 KB
65 AC 70 ms 3988 KB
66 AC 102 ms 4136 KB
67 AC 73 ms 4004 KB
68 AC 36 ms 3884 KB
69 AC 31 ms 3880 KB
7 AC 29 ms 3872 KB
70 AC 34 ms 3880 KB
71 AC 30 ms 3872 KB
72 AC 28 ms 3876 KB
73 AC 30 ms 3876 KB
74 AC 31 ms 3872 KB
75 AC 33 ms 3868 KB
76 AC 41 ms 3876 KB
77 AC 34 ms 3876 KB
78 AC 37 ms 3876 KB
79 AC 33 ms 3876 KB
8 AC 30 ms 3872 KB
80 AC 32 ms 3884 KB
81 AC 39 ms 3868 KB
82 AC 35 ms 3868 KB
83 AC 35 ms 3872 KB
84 AC 43 ms 3876 KB
85 AC 43 ms 3876 KB
86 AC 35 ms 3936 KB
87 AC 35 ms 3872 KB
88 AC 35 ms 3872 KB
89 AC 43 ms 3932 KB
9 AC 30 ms 3880 KB