답안 #20547 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20547	2017-02-12T09:36:50 Z	CodingAmolang(#71, sys7961)	초음속철도 (OJUZ11_rail)	C++11	45 / 100	3000 ms	524288 KB

rail

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using std::queue;
using std::vector;

const long long MOD = 1000000007;
struct segment_tree {
	vector<long long> tree;
	vector<queue<long long>> lazy;
	int k = 1;
	int n;
	segment_tree(int n):n(n) {
		while (k <= n)k *= 2;
		tree.resize(k*3);
		lazy.resize(k*3);
	}
	void update_lazy(int node, int start, int end) {

		std::queue<long long>& que = lazy[node];
		while (!que.empty()) {
			long long p = que.front();
			que.pop();
			if (p == -1) {
				tree[node] *= 2;
				tree[node] %= MOD;
			}
			else {
				tree[node] += p;
				tree[node] %= MOD;
			}
			if (start != end) {
				lazy[node * 2].push(p);
				lazy[node * 2 + 1].push(p);
			}
		}
	}
	void update_range(int node, int start, int end, int left, int right, long long diff) {
		update_lazy( node, start, end);
		if (left > end || right < start) {
			return;
		}
		if (left <= start && end <= right) {
			if (diff == -1) {
				tree[node] *= 2;
				tree[node] %= MOD;
			}
			else {
				tree[node] += diff;
				tree[node] %= MOD;
			}
			if (start != end) {
				lazy[node * 2].push(diff);
				lazy[node * 2 + 1].push(diff);
			}
			return;
		}
		update_range(node * 2, start, (start + end) / 2, left, right, diff);
		update_range(node * 2 + 1, (start + end) / 2 + 1, end, left, right, diff);
		tree[node] = (tree[node * 2] + tree[node * 2 + 1])%MOD;
	}
	long long sum(int node, int start, int end,int left, int right) {
		update_lazy(node, start, end);
		if (left > end || right < start) {
			return 0;
		}
		if (left <= start && end <= right) {
			return tree[node];
		}
		return sum(node * 2, start, (start + end) / 2, left, right) + sum( node * 2 + 1, (start + end) / 2 + 1, end, left, right);
	}
	long long getSum(int left, int right) {
		return sum(1, 0, n - 1, left, right);
	}
	void update(int left, int right, long long diff) {
		update_range(1, 0, n - 1, left, right, diff);
	}
};

using std::pair;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<long long> X = { 1,n };
	vector<pair<long long, long long>> seg;
	for (int i = 0; i < m; i++) {
		long long s, e;
		scanf("%lld%lld", &s, &e);
		seg.push_back({ s,e });
		X.push_back(s);
		X.push_back(e);
	}
	std::sort(seg.begin(), seg.end());
	std::sort(X.begin(), X.end());
	X.erase(std::unique(X.begin(), X.end()), X.end());
	segment_tree tree(X.size());
	tree.update(0,0, 1);
	for (auto segment : seg) {
		long long s = std::lower_bound(X.begin(),X.end(),segment.first)-X.begin();
		long long e = std::lower_bound(X.begin(),X.end(),segment.second)-X.begin();
		tree.update(e,e, tree.getSum(s, e));
		tree.update(e + 1, X.size() - 1, -1);
	}
	printf("%lld", tree.getSum(X.size() - 1, X.size() - 1));
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:84:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
rail.cpp:89:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &s, &e);
                            ^

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1956 KB	Output is correct
2	Correct	2088 KB	Output is correct
3	Correct	2088 KB	Output is correct
4	Correct	2088 KB	Output is correct
5	Correct	1956 KB	Output is correct
6	Correct	1956 KB	Output is correct
7	Correct	1956 KB	Output is correct
8	Correct	2088 KB	Output is correct
9	Correct	1956 KB	Output is correct
10	Correct	1956 KB	Output is correct
11	Correct	1956 KB	Output is correct
12	Correct	2088 KB	Output is correct
13	Correct	1956 KB	Output is correct
14	Correct	1956 KB	Output is correct
15	Correct	1956 KB	Output is correct
16	Correct	1956 KB	Output is correct
17	Correct	1956 KB	Output is correct
18	Correct	2088 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	1956 KB	Output is correct
2	Correct	2088 KB	Output is correct
3	Correct	2088 KB	Output is correct
4	Correct	2088 KB	Output is correct
5	Correct	1956 KB	Output is correct
6	Correct	1956 KB	Output is correct
7	Correct	1956 KB	Output is correct
8	Correct	2088 KB	Output is correct
9	Correct	1956 KB	Output is correct
10	Correct	1956 KB	Output is correct
11	Correct	1956 KB	Output is correct
12	Correct	2088 KB	Output is correct
13	Correct	1956 KB	Output is correct
14	Correct	1956 KB	Output is correct
15	Correct	1956 KB	Output is correct
16	Correct	1956 KB	Output is correct
17	Correct	1956 KB	Output is correct
18	Correct	2088 KB	Output is correct
19	Correct	2088 KB	Output is correct
20	Correct	2088 KB	Output is correct
21	Correct	2088 KB	Output is correct
22	Correct	2088 KB	Output is correct
23	Correct	2088 KB	Output is correct
24	Correct	2088 KB	Output is correct
25	Correct	2088 KB	Output is correct
26	Correct	2088 KB	Output is correct
27	Correct	2088 KB	Output is correct
28	Correct	1956 KB	Output is correct
29	Correct	2088 KB	Output is correct
30	Correct	2088 KB	Output is correct
31	Correct	2088 KB	Output is correct
32	Correct	2088 KB	Output is correct
33	Correct	2088 KB	Output is correct
34	Correct	2088 KB	Output is correct
35	Correct	2088 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1956 KB	Output is correct
2	Correct	0 ms	1956 KB	Output is correct
3	Correct	0 ms	1956 KB	Output is correct
4	Correct	53 ms	8856 KB	Output is correct
5	Execution timed out	3000 ms	259640 KB	Execution timed out
6	Memory limit exceeded	389 ms	524288 KB	Memory limit exceeded
7	Memory limit exceeded	336 ms	524288 KB	Memory limit exceeded
8	Correct	0 ms	2216 KB	Output is correct
9	Memory limit exceeded	363 ms	524288 KB	Memory limit exceeded
10	Memory limit exceeded	379 ms	524288 KB	Memory limit exceeded
11	Execution timed out	3000 ms	270068 KB	Execution timed out
12	Memory limit exceeded	356 ms	524288 KB	Memory limit exceeded
13	Memory limit exceeded	403 ms	524288 KB	Memory limit exceeded
14	Correct	66 ms	12368 KB	Output is correct
15	Memory limit exceeded	469 ms	524288 KB	Memory limit exceeded
16	Correct	76 ms	12368 KB	Output is correct
17	Memory limit exceeded	393 ms	524288 KB	Memory limit exceeded
18	Memory limit exceeded	389 ms	524288 KB	Memory limit exceeded
19	Memory limit exceeded	393 ms	524288 KB	Memory limit exceeded

Subtask #4
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1956 KB	Output is correct
2	Correct	0 ms	2088 KB	Output is correct
3	Correct	0 ms	2088 KB	Output is correct
4	Correct	0 ms	2088 KB	Output is correct
5	Correct	0 ms	1956 KB	Output is correct
6	Correct	0 ms	1956 KB	Output is correct
7	Correct	0 ms	1956 KB	Output is correct
8	Correct	0 ms	2088 KB	Output is correct
9	Correct	0 ms	1956 KB	Output is correct
10	Correct	0 ms	1956 KB	Output is correct
11	Correct	0 ms	1956 KB	Output is correct
12	Correct	0 ms	2088 KB	Output is correct
13	Correct	0 ms	1956 KB	Output is correct
14	Correct	0 ms	1956 KB	Output is correct
15	Correct	0 ms	1956 KB	Output is correct
16	Correct	0 ms	1956 KB	Output is correct
17	Correct	0 ms	1956 KB	Output is correct
18	Correct	0 ms	2088 KB	Output is correct
19	Correct	0 ms	2088 KB	Output is correct
20	Correct	0 ms	2088 KB	Output is correct
21	Correct	0 ms	2088 KB	Output is correct
22	Correct	0 ms	2088 KB	Output is correct
23	Correct	0 ms	2088 KB	Output is correct
24	Correct	0 ms	2088 KB	Output is correct
25	Correct	0 ms	2088 KB	Output is correct
26	Correct	0 ms	2088 KB	Output is correct
27	Correct	0 ms	2088 KB	Output is correct
28	Correct	0 ms	1956 KB	Output is correct
29	Correct	0 ms	2088 KB	Output is correct
30	Correct	0 ms	2088 KB	Output is correct
31	Correct	0 ms	2088 KB	Output is correct
32	Correct	0 ms	2088 KB	Output is correct
33	Correct	0 ms	2088 KB	Output is correct
34	Correct	0 ms	2088 KB	Output is correct
35	Correct	0 ms	2088 KB	Output is correct
36	Correct	483 ms	70916 KB	Output is correct
37	Correct	319 ms	43804 KB	Output is correct
38	Correct	119 ms	15852 KB	Output is correct
39	Correct	0 ms	2248 KB	Output is correct
40	Correct	276 ms	26356 KB	Output is correct
41	Correct	489 ms	60884 KB	Output is correct
42	Correct	436 ms	69728 KB	Output is correct
43	Correct	0 ms	2088 KB	Output is correct
44	Correct	326 ms	42196 KB	Output is correct
45	Correct	0 ms	2248 KB	Output is correct
46	Correct	136 ms	32428 KB	Output is correct
47	Correct	216 ms	36256 KB	Output is correct
48	Correct	219 ms	35728 KB	Output is correct
49	Correct	3 ms	2904 KB	Output is correct
50	Correct	3 ms	2640 KB	Output is correct
51	Correct	3 ms	2772 KB	Output is correct
52	Correct	16 ms	7552 KB	Output is correct
53	Correct	539 ms	73820 KB	Output is correct
54	Correct	79 ms	16220 KB	Output is correct
55	Correct	466 ms	71048 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1956 KB	Output is correct
2	Correct	0 ms	2088 KB	Output is correct
3	Correct	0 ms	2088 KB	Output is correct
4	Correct	0 ms	2088 KB	Output is correct
5	Correct	0 ms	1956 KB	Output is correct
6	Correct	0 ms	1956 KB	Output is correct
7	Correct	0 ms	1956 KB	Output is correct
8	Correct	0 ms	2088 KB	Output is correct
9	Correct	0 ms	1956 KB	Output is correct
10	Correct	0 ms	1956 KB	Output is correct
11	Correct	0 ms	1956 KB	Output is correct
12	Correct	0 ms	2088 KB	Output is correct
13	Correct	0 ms	1956 KB	Output is correct
14	Correct	0 ms	1956 KB	Output is correct
15	Correct	0 ms	1956 KB	Output is correct
16	Correct	0 ms	1956 KB	Output is correct
17	Correct	0 ms	1956 KB	Output is correct
18	Correct	0 ms	2088 KB	Output is correct
19	Correct	0 ms	2088 KB	Output is correct
20	Correct	0 ms	2088 KB	Output is correct
21	Correct	0 ms	2088 KB	Output is correct
22	Correct	0 ms	2088 KB	Output is correct
23	Correct	0 ms	2088 KB	Output is correct
24	Correct	0 ms	2088 KB	Output is correct
25	Correct	0 ms	2088 KB	Output is correct
26	Correct	0 ms	2088 KB	Output is correct
27	Correct	0 ms	2088 KB	Output is correct
28	Correct	0 ms	1956 KB	Output is correct
29	Correct	0 ms	2088 KB	Output is correct
30	Correct	0 ms	2088 KB	Output is correct
31	Correct	0 ms	2088 KB	Output is correct
32	Correct	0 ms	2088 KB	Output is correct
33	Correct	0 ms	2088 KB	Output is correct
34	Correct	0 ms	2088 KB	Output is correct
35	Correct	0 ms	2088 KB	Output is correct
36	Correct	0 ms	1956 KB	Output is correct
37	Correct	0 ms	1956 KB	Output is correct
38	Correct	0 ms	1956 KB	Output is correct
39	Correct	53 ms	8856 KB	Output is correct
40	Execution timed out	3000 ms	259640 KB	Execution timed out
41	Memory limit exceeded	389 ms	524288 KB	Memory limit exceeded
42	Memory limit exceeded	336 ms	524288 KB	Memory limit exceeded
43	Correct	0 ms	2216 KB	Output is correct
44	Memory limit exceeded	363 ms	524288 KB	Memory limit exceeded
45	Memory limit exceeded	379 ms	524288 KB	Memory limit exceeded
46	Execution timed out	3000 ms	270068 KB	Execution timed out
47	Memory limit exceeded	356 ms	524288 KB	Memory limit exceeded
48	Memory limit exceeded	403 ms	524288 KB	Memory limit exceeded
49	Correct	66 ms	12368 KB	Output is correct
50	Memory limit exceeded	469 ms	524288 KB	Memory limit exceeded
51	Correct	76 ms	12368 KB	Output is correct
52	Memory limit exceeded	393 ms	524288 KB	Memory limit exceeded
53	Memory limit exceeded	389 ms	524288 KB	Memory limit exceeded
54	Memory limit exceeded	393 ms	524288 KB	Memory limit exceeded
55	Correct	483 ms	70916 KB	Output is correct
56	Correct	319 ms	43804 KB	Output is correct
57	Correct	119 ms	15852 KB	Output is correct
58	Correct	0 ms	2248 KB	Output is correct
59	Correct	276 ms	26356 KB	Output is correct
60	Correct	489 ms	60884 KB	Output is correct
61	Correct	436 ms	69728 KB	Output is correct
62	Correct	0 ms	2088 KB	Output is correct
63	Correct	326 ms	42196 KB	Output is correct
64	Correct	0 ms	2248 KB	Output is correct
65	Correct	136 ms	32428 KB	Output is correct
66	Correct	216 ms	36256 KB	Output is correct
67	Correct	219 ms	35728 KB	Output is correct
68	Correct	3 ms	2904 KB	Output is correct
69	Correct	3 ms	2640 KB	Output is correct
70	Correct	3 ms	2772 KB	Output is correct
71	Correct	16 ms	7552 KB	Output is correct
72	Correct	539 ms	73820 KB	Output is correct
73	Correct	79 ms	16220 KB	Output is correct
74	Correct	466 ms	71048 KB	Output is correct
75	Memory limit exceeded	433 ms	524288 KB	Memory limit exceeded
76	Memory limit exceeded	393 ms	524288 KB	Memory limit exceeded
77	Execution timed out	3000 ms	30692 KB	Execution timed out
78	Correct	73 ms	12368 KB	Output is correct
79	Memory limit exceeded	2469 ms	524288 KB	Memory limit exceeded
80	Memory limit exceeded	373 ms	524288 KB	Memory limit exceeded
81	Correct	226 ms	30712 KB	Output is correct
82	Memory limit exceeded	383 ms	524288 KB	Memory limit exceeded
83	Correct	53 ms	12368 KB	Output is correct
84	Memory limit exceeded	389 ms	524288 KB	Memory limit exceeded
85	Memory limit exceeded	429 ms	524288 KB	Memory limit exceeded
86	Memory limit exceeded	406 ms	524288 KB	Memory limit exceeded
87	Correct	176 ms	19976 KB	Output is correct
88	Correct	186 ms	28864 KB	Output is correct
89	Memory limit exceeded	439 ms	524288 KB	Memory limit exceeded
90	Memory limit exceeded	429 ms	524288 KB	Memory limit exceeded
91	Memory limit exceeded	369 ms	524288 KB	Memory limit exceeded
92	Memory limit exceeded	456 ms	524288 KB	Memory limit exceeded
93	Memory limit exceeded	476 ms	524288 KB	Memory limit exceeded
94	Memory limit exceeded	406 ms	524288 KB	Memory limit exceeded
95	Memory limit exceeded	386 ms	524288 KB	Memory limit exceeded

답안 #20547

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