oj.uz

답안 #163743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163743 2019-11-15T05:00:58 Z jwvg0425 초음속철도 (OJUZ11_rail) C++17
10 / 100
 300 ms 6904 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9 + 7)

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

class Mapping
{
public:
	void init(const vector<int>& raw, int base = 0)
	{
		start = base;
		arr = raw;
		sort(arr.begin(), arr.end());
		arr.erase(unique(arr.begin(), arr.end()), arr.end());
	}

	int get_idx(int k)
	{
		return start + (lower_bound(all(arr), k) - arr.begin());
	}

	int get_value(int idx)
	{
		return arr[idx - start];
	}

	int size()
	{
		return arr.size();
	}

private:
	int start;
	vector<int> arr;
};

i64 two[200005];

void updateLazy(vector<i64>& tree, vector<i64>& lazy, int start, int end, int node)
{
	if (lazy[node] == 0)
		return;

	tree[node] = (tree[node] * two[lazy[node]]) % MOD;

	if (start != end)
	{
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}

	lazy[node] = 0;
}

// * 2
void multRange(vector<i64>& tree, vector<i64>& lazy, int start, int end, int node, int left, int right)
{
	updateLazy(tree, lazy, start, end, node);

	if (left > end || right < start)
		return;

	if (left <= start && end <= right)
	{
		tree[node] = (tree[node] * 2) % MOD;

		if (start != end)
		{
			lazy[node * 2] += 1;
			lazy[node * 2 + 1] += 1;
		}

		return;
	}

	int mid = (start + end) / 2;
	multRange(tree, lazy, start, mid, node * 2, left, right);
	multRange(tree, lazy, mid + 1, end, node * 2 + 1, left, right);
	tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % MOD;
}

void add(vector<i64>& tree, vector<i64>& lazy, int start, int end, int node, int pos, i64 diff)
{
	updateLazy(tree, lazy, start, end, node);

	if (pos > end || pos < start)
		return;

	if (start == end)
	{
		tree[node] = (tree[node] + diff) % MOD;
		return;
	}

	int mid = (start + end) / 2;
	add(tree, lazy, start, mid, node * 2, pos, diff);
	add(tree, lazy, mid + 1, end, node * 2 + 1, pos, diff);
	tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % MOD;
}

i64 query(vector<i64>& tree, vector<i64>& lazy, int start, int end, int node, int left, int right)
{
	updateLazy(tree, lazy, start, end, node);

	if (left > end || right < start)
		return 0;

	if (left <= start && end <= right)
		return tree[node];

	int mid = (start + end) / 2;
	return query(tree, lazy, start, mid, node * 2, left, right) +
		query(tree, lazy, mid + 1, end, node * 2 + 1, left, right);
}


int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	vector<ii> train(m);
	vector<int> pos = { 1, n };

	two[0] = 1;

	for (int i = 1; i <= n + 5; i++)
		two[i] = (two[i - 1] * 2) % MOD;

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &train[i].xx, &train[i].yy);
		pos.push_back(train[i].xx);
		pos.push_back(train[i].yy);
	}

	Mapping mapping;
	mapping.init(pos);

	for (int i = 0; i < m; i++)
	{
		train[i].xx = mapping.get_idx(train[i].xx);
		train[i].yy = mapping.get_idx(train[i].yy);
	}

	sort(all(train));

	int k = mapping.size();
	vector<i64> tree(k * 8);
	vector<i64> lazy(k * 8);

	add(tree, lazy, 0, k, 1, 0, 1);

	for (int i = 0; i < m; i++)
	{
		// 모든 구간에 대해 경우의 수 유지하며 다음 단계로
		// train[i].yy 지점에서 train[i].xx ~ train[i].yy 까지 전부 더함
		i64 q = query(tree, lazy, 0, k, 1, train[i].xx, train[i].yy);
		add(tree, lazy, 0, k, 1, train[i].yy, q);

		// train[i].yy 지점 이후는 값이 2배씩 상승함(train[i] 고르거나 안 고르거나)
		multRange(tree, lazy, 0, k, 1, train[i].yy + 1, k);
	}

	printf("%lld\n", query(tree, lazy, 0, k, 1, k - 1, k - 1));

	return 0;
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
rail.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &train[i].xx, &train[i].yy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 128 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 7 ms 3724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Correct 2 ms 376 KB Output is correct
23 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 7 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 10 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Correct 2 ms 256 KB Output is correct
32 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 2 ms 376 KB Output is correct
35 Runtime error 7 ms 3676 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 11 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 11 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 11 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 2 ms 376 KB Output is correct
9 Runtime error 10 ms 6524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 9 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 11 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 9 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 12 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 11 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 128 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 7 ms 3724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Correct 2 ms 376 KB Output is correct
23 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 7 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 10 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Correct 2 ms 256 KB Output is correct
32 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 2 ms 376 KB Output is correct
35 Runtime error 7 ms 3676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Incorrect 9 ms 760 KB Output isn't correct
39 Incorrect 4 ms 504 KB Output isn't correct
40 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Correct 2 ms 256 KB Output is correct
44 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 7 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 128 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 7 ms 3724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Correct 2 ms 376 KB Output is correct
23 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 7 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 10 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Correct 2 ms 256 KB Output is correct
32 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Correct 2 ms 376 KB Output is correct
35 Runtime error 7 ms 3676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Correct 2 ms 252 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 11 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 11 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 11 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Correct 2 ms 376 KB Output is correct
44 Runtime error 10 ms 6524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 10 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 9 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 11 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 9 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 12 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 11 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 5 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Incorrect 9 ms 760 KB Output isn't correct
58 Incorrect 4 ms 504 KB Output isn't correct
59 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Correct 2 ms 256 KB Output is correct
63 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 7 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 7 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 7 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 9 ms 5748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Incorrect 300 ms 5268 KB Output isn't correct
78 Incorrect 95 ms 5224 KB Output isn't correct
79 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 13 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Correct 11 ms 1116 KB Output is correct
82 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 11 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 10 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 10 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 10 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 10 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 10 ms 6876 KB Execution killed with signal 11 (could be triggered by violating memory limits)