Submission #20552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20552	2017-02-12T09:46:03 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 int MOD = 1000000007;
struct segment_tree {
	vector<int> tree;
	vector<queue<int>> 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<int>& que = lazy[node];
		while (!que.empty()) {
			int 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, int 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;
	}
	int 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))%MOD;
	}
	int getSum(int left, int right) {
		return sum(1, 0, n - 1, left, right);
	}
	void update(int left, int right, int diff) {
		update_range(1, 0, n - 1, left, right, diff);
	}
};

using std::pair;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> X = { 1,n };
	vector<pair<int, int>> seg;
	for (int i = 0; i < m; i++) {
		int s, e;
		scanf("%d%d", &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) {
		int s = std::lower_bound(X.begin(),X.end(),segment.first)-X.begin();
		int 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("%d", 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:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
                        ^

Subtask #1
10.0 / 10.0

#	Verdict	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	49 ms	7540 KB	Output is correct
5	Execution timed out	3000 ms	204560 KB	Execution timed out
6	Memory limit exceeded	439 ms	524288 KB	Memory limit exceeded
7	Memory limit exceeded	403 ms	524288 KB	Memory limit exceeded
8	Correct	0 ms	2216 KB	Output is correct
9	Memory limit exceeded	379 ms	524288 KB	Memory limit exceeded
10	Memory limit exceeded	369 ms	524288 KB	Memory limit exceeded
11	Execution timed out	3000 ms	211328 KB	Execution timed out
12	Memory limit exceeded	386 ms	524288 KB	Memory limit exceeded
13	Memory limit exceeded	413 ms	524288 KB	Memory limit exceeded
14	Correct	79 ms	7248 KB	Output is correct
15	Memory limit exceeded	443 ms	524288 KB	Memory limit exceeded
16	Correct	79 ms	7248 KB	Output is correct
17	Memory limit exceeded	396 ms	524288 KB	Memory limit exceeded
18	Memory limit exceeded	409 ms	524288 KB	Memory limit exceeded
19	Memory limit exceeded	423 ms	524288 KB	Memory limit exceeded

Subtask #4
27.0 / 27.0

#	Verdict	Execution time	Memory	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	399 ms	52640 KB	Output is correct
37	Correct	273 ms	30680 KB	Output is correct
38	Correct	99 ms	12948 KB	Output is correct
39	Correct	0 ms	2116 KB	Output is correct
40	Correct	223 ms	22824 KB	Output is correct
41	Correct	426 ms	47888 KB	Output is correct
42	Correct	383 ms	51980 KB	Output is correct
43	Correct	0 ms	2088 KB	Output is correct
44	Correct	303 ms	30348 KB	Output is correct
45	Correct	0 ms	2116 KB	Output is correct
46	Correct	126 ms	25464 KB	Output is correct
47	Correct	206 ms	27312 KB	Output is correct
48	Correct	196 ms	26916 KB	Output is correct
49	Correct	3 ms	2504 KB	Output is correct
50	Correct	3 ms	2376 KB	Output is correct
51	Correct	3 ms	2504 KB	Output is correct
52	Correct	19 ms	6844 KB	Output is correct
53	Correct	433 ms	54356 KB	Output is correct
54	Correct	73 ms	13032 KB	Output is correct
55	Correct	423 ms	52640 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	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	49 ms	7540 KB	Output is correct
40	Execution timed out	3000 ms	204560 KB	Execution timed out
41	Memory limit exceeded	439 ms	524288 KB	Memory limit exceeded
42	Memory limit exceeded	403 ms	524288 KB	Memory limit exceeded
43	Correct	0 ms	2216 KB	Output is correct
44	Memory limit exceeded	379 ms	524288 KB	Memory limit exceeded
45	Memory limit exceeded	369 ms	524288 KB	Memory limit exceeded
46	Execution timed out	3000 ms	211328 KB	Execution timed out
47	Memory limit exceeded	386 ms	524288 KB	Memory limit exceeded
48	Memory limit exceeded	413 ms	524288 KB	Memory limit exceeded
49	Correct	79 ms	7248 KB	Output is correct
50	Memory limit exceeded	443 ms	524288 KB	Memory limit exceeded
51	Correct	79 ms	7248 KB	Output is correct
52	Memory limit exceeded	396 ms	524288 KB	Memory limit exceeded
53	Memory limit exceeded	409 ms	524288 KB	Memory limit exceeded
54	Memory limit exceeded	423 ms	524288 KB	Memory limit exceeded
55	Correct	399 ms	52640 KB	Output is correct
56	Correct	273 ms	30680 KB	Output is correct
57	Correct	99 ms	12948 KB	Output is correct
58	Correct	0 ms	2116 KB	Output is correct
59	Correct	223 ms	22824 KB	Output is correct
60	Correct	426 ms	47888 KB	Output is correct
61	Correct	383 ms	51980 KB	Output is correct
62	Correct	0 ms	2088 KB	Output is correct
63	Correct	303 ms	30348 KB	Output is correct
64	Correct	0 ms	2116 KB	Output is correct
65	Correct	126 ms	25464 KB	Output is correct
66	Correct	206 ms	27312 KB	Output is correct
67	Correct	196 ms	26916 KB	Output is correct
68	Correct	3 ms	2504 KB	Output is correct
69	Correct	3 ms	2376 KB	Output is correct
70	Correct	3 ms	2504 KB	Output is correct
71	Correct	19 ms	6844 KB	Output is correct
72	Correct	433 ms	54356 KB	Output is correct
73	Correct	73 ms	13032 KB	Output is correct
74	Correct	423 ms	52640 KB	Output is correct
75	Memory limit exceeded	406 ms	524288 KB	Memory limit exceeded
76	Memory limit exceeded	399 ms	524288 KB	Memory limit exceeded
77	Execution timed out	3000 ms	20344 KB	Execution timed out
78	Correct	69 ms	7248 KB	Output is correct
79	Memory limit exceeded	2489 ms	524288 KB	Memory limit exceeded
80	Memory limit exceeded	399 ms	524288 KB	Memory limit exceeded
81	Correct	186 ms	24408 KB	Output is correct
82	Memory limit exceeded	419 ms	524288 KB	Memory limit exceeded
83	Correct	59 ms	7248 KB	Output is correct
84	Memory limit exceeded	366 ms	524288 KB	Memory limit exceeded
85	Memory limit exceeded	439 ms	524288 KB	Memory limit exceeded
86	Memory limit exceeded	473 ms	524288 KB	Memory limit exceeded
87	Correct	153 ms	11104 KB	Output is correct
88	Correct	166 ms	15644 KB	Output is correct
89	Memory limit exceeded	419 ms	524288 KB	Memory limit exceeded
90	Memory limit exceeded	433 ms	524288 KB	Memory limit exceeded
91	Memory limit exceeded	399 ms	524288 KB	Memory limit exceeded
92	Memory limit exceeded	396 ms	524288 KB	Memory limit exceeded
93	Memory limit exceeded	429 ms	524288 KB	Memory limit exceeded
94	Memory limit exceeded	399 ms	524288 KB	Memory limit exceeded
95	Memory limit exceeded	426 ms	524288 KB	Memory limit exceeded

Submission #20552

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