Japan Alumni Group Summer Camp 2013 Warming Up

Submission #813862

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

	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ソースコード長 1745 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 46 ms 864 KB
10 WA
11 AC 27 ms 928 KB
12 WA
13 AC 27 ms 824 KB
14 AC 27 ms 924 KB
15 AC 27 ms 920 KB
16 WA
17 WA
18 AC 27 ms 924 KB
19 WA
2 AC 29 ms 868 KB
20 WA
21 AC 27 ms 924 KB
22 AC 26 ms 808 KB
23 AC 27 ms 920 KB
24 AC 27 ms 920 KB
25 AC 26 ms 808 KB
26 AC 27 ms 832 KB
27 WA
28 AC 28 ms 920 KB
29 AC 27 ms 924 KB
3 AC 26 ms 924 KB
30 AC 28 ms 924 KB
31 WA
32 AC 27 ms 928 KB
33 AC 28 ms 928 KB
34 AC 26 ms 856 KB
35 WA
36 AC 27 ms 928 KB
37 AC 27 ms 928 KB
38 WA
39 AC 26 ms 920 KB
4 AC 26 ms 924 KB
40 AC 40 ms 880 KB
41 WA
42 WA
43 WA
44 AC 27 ms 928 KB
45 WA
46 AC 28 ms 928 KB
47 WA
48 AC 27 ms 920 KB
49 AC 26 ms 924 KB
5 AC 28 ms 800 KB
50 AC 27 ms 924 KB
51 WA
52 AC 27 ms 920 KB
53 AC 28 ms 924 KB
54 AC 27 ms 924 KB
55 WA
56 AC 29 ms 928 KB
57 AC 27 ms 808 KB
58 RE
59 RE
6 AC 28 ms 920 KB
60 RE
61 RE
62 RE
63 RE
64 RE
65 AC 86 ms 5808 KB
66 AC 137 ms 10036 KB
67 WA
68 AC 37 ms 1824 KB
69 AC 28 ms 960 KB
7 AC 28 ms 800 KB
70 AC 32 ms 1436 KB
71 WA
72 AC 29 ms 1052 KB
73 AC 30 ms 960 KB
74 AC 33 ms 1436 KB
75 WA
76 AC 45 ms 2360 KB
77 AC 37 ms 1820 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 29 ms 920 KB