Japan Alumni Group Summer Camp 2013 Warming Up

Submission #813931

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 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,20)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状態 WA
Score得点 0
Source lengthソースコード長 1861 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 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 30 ms 932 KB
10 AC 28 ms 944 KB
11 AC 35 ms 940 KB
12 AC 28 ms 944 KB
13 AC 27 ms 948 KB
14 AC 27 ms 1052 KB
15 AC 28 ms 948 KB
16 WA
17 WA
18 AC 27 ms 1052 KB
19 AC 25 ms 920 KB
2 AC 26 ms 1048 KB
20 WA
21 AC 27 ms 944 KB
22 AC 24 ms 948 KB
23 AC 25 ms 864 KB
24 AC 26 ms 1052 KB
25 AC 26 ms 1052 KB
26 AC 24 ms 1052 KB
27 AC 26 ms 1044 KB
28 AC 24 ms 972 KB
29 AC 26 ms 1056 KB
3 AC 25 ms 1048 KB
30 AC 26 ms 948 KB
31 WA
32 AC 24 ms 1048 KB
33 AC 26 ms 948 KB
34 AC 27 ms 948 KB
35 AC 26 ms 1048 KB
36 AC 30 ms 1040 KB
37 AC 26 ms 944 KB
38 WA
39 AC 24 ms 948 KB
4 AC 26 ms 944 KB
40 AC 27 ms 948 KB
41 WA
42 AC 26 ms 948 KB
43 WA
44 AC 26 ms 1048 KB
45 WA
46 AC 26 ms 1052 KB
47 WA
48 AC 26 ms 1048 KB
49 AC 26 ms 1048 KB
5 AC 24 ms 1044 KB
50 AC 26 ms 1052 KB
51 WA
52 AC 26 ms 1056 KB
53 AC 27 ms 1052 KB
54 AC 26 ms 1048 KB
55 WA
56 AC 26 ms 948 KB
57 AC 26 ms 1052 KB
58 AC 254 ms 21400 KB
59 WA
6 AC 27 ms 940 KB
60 AC 259 ms 21408 KB
61 WA
62 WA
63 WA
64 WA
65 AC 99 ms 6696 KB
66 AC 164 ms 11712 KB
67 WA
68 AC 38 ms 2096 KB
69 AC 28 ms 1112 KB
7 WA
70 AC 33 ms 1712 KB
71 WA
72 AC 27 ms 1184 KB
73 AC 25 ms 1068 KB
74 AC 31 ms 1460 KB
75 WA
76 AC 42 ms 2604 KB
77 AC 37 ms 1968 KB
78 WA
79 WA
8 WA
80 WA
81 WA
82 WA
83 WA
84 WA
85 WA
86 WA
87 WA
88 WA
89 WA
9 AC 26 ms 1048 KB