Submission #163744

#	Time	Username	Problem	Language	Result	Execution time	Memory
163744		jwvg0425	초음속철도 (OJUZ11_rail)	C++17	100 / 100	717 ms	56948 KiB

rail

#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[300005];

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 <= m + 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 (stderr)

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 / 10
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30