Japan Alumni Group Summer Camp 2013 Warming Up

Submission #813937

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