Submission #20563

#	Time	Username	Problem	Language	Result	Execution time	Memory
20563		CodingAmolang (#35)	초음속철도 (OJUZ11_rail)	C++11	100 / 100	726 ms	34896 KiB

rail

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

const long long MOD = 1000000007;
long long poww(long long a, long long b) {
	if (b == 0)return 1;
	long long tmp = poww(a, b / 2);
	if (b % 2 == 1)return (((tmp*tmp) % MOD)*a) % MOD;
	return (tmp*tmp) % MOD;
}
struct segment_tree {
	vector<long long> tree;
	vector<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,1);
	}
	void update_lazy(int node, int start, int end) {
		if (lazy[node] != 1) {
			tree[node] *= lazy[node];
			tree[node] %= MOD;
			if (start != end) {
				lazy[node * 2] *= lazy[node];
				lazy[node * 2 + 1] *= lazy[node];
				lazy[node * 2] %= MOD;
				lazy[node * 2 + 1] %= MOD;
			}
			lazy[node] = 1;
		}
	}
	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) {
			tree[node] *= diff;
			tree[node] %= MOD;
			if (start != end) {
				lazy[node * 2] *= diff;
				lazy[node * 2 + 1]*=diff;
				lazy[node * 2] %= MOD;
				lazy[node * 2 + 1] %= MOD;
			}
			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;
	}
	void update_one(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) {
			tree[node] += diff;
			tree[node] %= MOD;
			return;
		}
		update_one(node * 2, start, (start + end) / 2, left, right, diff);
		update_one(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);
	}
	void update_plus(int idx, long long a) {
		update_range(1, 0, n - 1, idx, idx, 1);
		update_one(1, 0, n - 1, idx, idx, a);
	}
};

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_plus(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_plus(e, tree.getSum(s, e));
		tree.update(e + 1, X.size() - 1, 2);
	}
	printf("%lld", tree.getSum(X.size() - 1, X.size() - 1));
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:97: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:102: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 / 10
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30