답안 #66241 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66241	2018-08-10T05:30:05 Z	윤교준(#1888)	초음속철도 (OJUZ11_rail)	C++11	45 / 100	3000 ms	8048 KB

rail

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1000000007;
const int MAXN = 200005;

inline void add(int &a, int b) { a += b; if(MOD <= a) a -= MOD; }

int dp[MAXN];
int A[MAXN], B[MAXN], O[MAXN];

int N, M;

int main() {
	ios::sync_with_stdio(false);

	cin >> M >> N;
	for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];

	{
		vector<int> V;
		V.eb(1); V.eb(M);
		for(int i = 1; i <= N; i++) {
			V.eb(A[i]);
			V.eb(B[i]);
		}
		sorv(V); univ(V);
		M = sz(V);
		for(int i = 1; i <= N; i++) {
			A[i] = int(lower_bound(allv(V), A[i]) - V.begin()) + 1;
			B[i] = int(lower_bound(allv(V), B[i]) - V.begin()) + 1;
		}
	}
	iota(O, O+N+1, 0);
	sort(O+1, O+N+1, [&](int a, int b) { return B[a] < B[b]; });

	dp[1] = 1;
	for(int oi = 1, i; oi <= N; oi++) {
		i = O[oi];
		int s = A[i], e = B[i], ret = 0;
		for(int i = s; i < e; i++) add(ret, dp[i]);
		for(int i = 1; i < s; i++) add(dp[i], dp[i]);
		for(int i = e; i <= M; i++) add(dp[i], dp[i]);
		add(dp[e], ret);
	}
	
	cout << dp[M] << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	420 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	3 ms	420 KB	Output is correct
7	Correct	3 ms	496 KB	Output is correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	2 ms	496 KB	Output is correct
10	Correct	2 ms	544 KB	Output is correct
11	Correct	2 ms	544 KB	Output is correct
12	Correct	2 ms	544 KB	Output is correct
13	Correct	2 ms	544 KB	Output is correct
14	Correct	2 ms	544 KB	Output is correct
15	Correct	3 ms	544 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	420 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	3 ms	420 KB	Output is correct
7	Correct	3 ms	496 KB	Output is correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	2 ms	496 KB	Output is correct
10	Correct	2 ms	544 KB	Output is correct
11	Correct	2 ms	544 KB	Output is correct
12	Correct	2 ms	544 KB	Output is correct
13	Correct	2 ms	544 KB	Output is correct
14	Correct	2 ms	544 KB	Output is correct
15	Correct	3 ms	544 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Correct	3 ms	620 KB	Output is correct
23	Correct	3 ms	736 KB	Output is correct
24	Correct	3 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	2 ms	736 KB	Output is correct
27	Correct	3 ms	736 KB	Output is correct
28	Correct	3 ms	736 KB	Output is correct
29	Correct	3 ms	736 KB	Output is correct
30	Correct	3 ms	736 KB	Output is correct
31	Correct	3 ms	736 KB	Output is correct
32	Correct	2 ms	736 KB	Output is correct
33	Correct	2 ms	736 KB	Output is correct
34	Correct	3 ms	736 KB	Output is correct
35	Correct	4 ms	736 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	736 KB	Output is correct
2	Correct	2 ms	736 KB	Output is correct
3	Correct	3 ms	736 KB	Output is correct
4	Correct	15 ms	748 KB	Output is correct
5	Execution timed out	3047 ms	4448 KB	Time limit exceeded
6	Runtime error	250 ms	7216 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	198 ms	7716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	3 ms	7716 KB	Output is correct
9	Runtime error	187 ms	7716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	228 ms	7788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Execution timed out	3045 ms	7788 KB	Time limit exceeded
12	Runtime error	240 ms	7820 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	199 ms	7992 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Correct	79 ms	8048 KB	Output is correct
15	Execution timed out	3066 ms	8048 KB	Time limit exceeded
16	Correct	95 ms	8048 KB	Output is correct
17	Runtime error	206 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	248 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	204 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	420 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	3 ms	420 KB	Output is correct
7	Correct	3 ms	496 KB	Output is correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	2 ms	496 KB	Output is correct
10	Correct	2 ms	544 KB	Output is correct
11	Correct	2 ms	544 KB	Output is correct
12	Correct	2 ms	544 KB	Output is correct
13	Correct	2 ms	544 KB	Output is correct
14	Correct	2 ms	544 KB	Output is correct
15	Correct	3 ms	544 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Correct	3 ms	620 KB	Output is correct
23	Correct	3 ms	736 KB	Output is correct
24	Correct	3 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	2 ms	736 KB	Output is correct
27	Correct	3 ms	736 KB	Output is correct
28	Correct	3 ms	736 KB	Output is correct
29	Correct	3 ms	736 KB	Output is correct
30	Correct	3 ms	736 KB	Output is correct
31	Correct	3 ms	736 KB	Output is correct
32	Correct	2 ms	736 KB	Output is correct
33	Correct	2 ms	736 KB	Output is correct
34	Correct	3 ms	736 KB	Output is correct
35	Correct	4 ms	736 KB	Output is correct
36	Correct	69 ms	8048 KB	Output is correct
37	Correct	50 ms	8048 KB	Output is correct
38	Correct	21 ms	8048 KB	Output is correct
39	Correct	4 ms	8048 KB	Output is correct
40	Correct	36 ms	8048 KB	Output is correct
41	Correct	76 ms	8048 KB	Output is correct
42	Correct	67 ms	8048 KB	Output is correct
43	Correct	2 ms	8048 KB	Output is correct
44	Correct	48 ms	8048 KB	Output is correct
45	Correct	4 ms	8048 KB	Output is correct
46	Correct	39 ms	8048 KB	Output is correct
47	Correct	52 ms	8048 KB	Output is correct
48	Correct	36 ms	8048 KB	Output is correct
49	Correct	5 ms	8048 KB	Output is correct
50	Correct	5 ms	8048 KB	Output is correct
51	Correct	5 ms	8048 KB	Output is correct
52	Correct	6 ms	8048 KB	Output is correct
53	Correct	72 ms	8048 KB	Output is correct
54	Correct	17 ms	8048 KB	Output is correct
55	Correct	72 ms	8048 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	416 KB	Output is correct
4	Correct	3 ms	420 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	3 ms	420 KB	Output is correct
7	Correct	3 ms	496 KB	Output is correct
8	Correct	3 ms	496 KB	Output is correct
9	Correct	2 ms	496 KB	Output is correct
10	Correct	2 ms	544 KB	Output is correct
11	Correct	2 ms	544 KB	Output is correct
12	Correct	2 ms	544 KB	Output is correct
13	Correct	2 ms	544 KB	Output is correct
14	Correct	2 ms	544 KB	Output is correct
15	Correct	3 ms	544 KB	Output is correct
16	Correct	2 ms	620 KB	Output is correct
17	Correct	2 ms	620 KB	Output is correct
18	Correct	2 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	2 ms	620 KB	Output is correct
22	Correct	3 ms	620 KB	Output is correct
23	Correct	3 ms	736 KB	Output is correct
24	Correct	3 ms	736 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	2 ms	736 KB	Output is correct
27	Correct	3 ms	736 KB	Output is correct
28	Correct	3 ms	736 KB	Output is correct
29	Correct	3 ms	736 KB	Output is correct
30	Correct	3 ms	736 KB	Output is correct
31	Correct	3 ms	736 KB	Output is correct
32	Correct	2 ms	736 KB	Output is correct
33	Correct	2 ms	736 KB	Output is correct
34	Correct	3 ms	736 KB	Output is correct
35	Correct	4 ms	736 KB	Output is correct
36	Correct	2 ms	736 KB	Output is correct
37	Correct	2 ms	736 KB	Output is correct
38	Correct	3 ms	736 KB	Output is correct
39	Correct	15 ms	748 KB	Output is correct
40	Execution timed out	3047 ms	4448 KB	Time limit exceeded
41	Runtime error	250 ms	7216 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	198 ms	7716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Correct	3 ms	7716 KB	Output is correct
44	Runtime error	187 ms	7716 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	228 ms	7788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Execution timed out	3045 ms	7788 KB	Time limit exceeded
47	Runtime error	240 ms	7820 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	199 ms	7992 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Correct	79 ms	8048 KB	Output is correct
50	Execution timed out	3066 ms	8048 KB	Time limit exceeded
51	Correct	95 ms	8048 KB	Output is correct
52	Runtime error	206 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	248 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	204 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Correct	69 ms	8048 KB	Output is correct
56	Correct	50 ms	8048 KB	Output is correct
57	Correct	21 ms	8048 KB	Output is correct
58	Correct	4 ms	8048 KB	Output is correct
59	Correct	36 ms	8048 KB	Output is correct
60	Correct	76 ms	8048 KB	Output is correct
61	Correct	67 ms	8048 KB	Output is correct
62	Correct	2 ms	8048 KB	Output is correct
63	Correct	48 ms	8048 KB	Output is correct
64	Correct	4 ms	8048 KB	Output is correct
65	Correct	39 ms	8048 KB	Output is correct
66	Correct	52 ms	8048 KB	Output is correct
67	Correct	36 ms	8048 KB	Output is correct
68	Correct	5 ms	8048 KB	Output is correct
69	Correct	5 ms	8048 KB	Output is correct
70	Correct	5 ms	8048 KB	Output is correct
71	Correct	6 ms	8048 KB	Output is correct
72	Correct	72 ms	8048 KB	Output is correct
73	Correct	17 ms	8048 KB	Output is correct
74	Correct	72 ms	8048 KB	Output is correct
75	Runtime error	208 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	136 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Correct	1002 ms	8048 KB	Output is correct
78	Correct	72 ms	8048 KB	Output is correct
79	Execution timed out	3049 ms	8048 KB	Time limit exceeded
80	Runtime error	226 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Correct	33 ms	8048 KB	Output is correct
82	Runtime error	206 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Correct	69 ms	8048 KB	Output is correct
84	Runtime error	206 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Execution timed out	3053 ms	8048 KB	Time limit exceeded
86	Execution timed out	3017 ms	8048 KB	Time limit exceeded
87	Correct	125 ms	8048 KB	Output is correct
88	Correct	103 ms	8048 KB	Output is correct
89	Runtime error	242 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	204 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	211 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	204 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
93	Execution timed out	3059 ms	8048 KB	Time limit exceeded
94	Runtime error	205 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
95	Runtime error	210 ms	8048 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #66241

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 8.0 / 8.0

Subtask #3 0 / 25.0

Subtask #4 27.0 / 27.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
8.0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
27.0 / 27.0

Subtask #5
0 / 30.0