Submission #20552

#TimeUsernameProblemLanguageResultExecution timeMemory
20552CodingAmolang (#35)초음속철도 (OJUZ11_rail)C++11
45 / 100
3000 ms524288 KiB
#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 (stderr)

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);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...