Japan Alumni Group Summer Camp 2013 Warming Up

Submission #813936

Source codeソースコード

#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=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
User nameユーザ名 Hec
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1861 Byte
File nameファイル名
Exec time実行時間 334 ms
Memory usageメモリ使用量 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