Submission #20543

#	Time	Username	Problem	Language	Result	Execution time	Memory
20543		CodingAmolang (#35)	초음속철도 (OJUZ11_rail)	C++11	45 / 100	3000 ms	22588 KiB

rail

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

const long long MOD = 1000000007;

struct indexed_tree {
	vector<long long> tree;
	int k = 1;
	indexed_tree(int n) {
		while (k <= n)k *= 2;
		tree.resize(k * 3, 0);
	}
	void update(int idx, int a) {
		tree[k + idx] += a;
		tree[k + idx] %= MOD;
		idx = (k + idx) / 2;
		while (idx) {
			tree[idx] = (tree[idx * 2] + tree[idx * 2 + 1])%MOD;
			idx /= 2;
		}
	}
	long long getSum(int l, int r) {
		l += k;
		r += k;
		long long ret = 0;
		while (l <= r) {
			if (l % 2 == 1)ret += tree[l];
			if (r % 2 == 0)ret += tree[r];
			ret %= MOD;
			l = (l + 1) / 2;
			r = (r - 1) / 2;
		}
		return ret;
	}
};
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());
	indexed_tree tree(X.size());
	tree.update(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(e, tree.getSum(s, e));
		for (int i = e + 1; i < X.size(); i++) {
			tree.update(i, tree.getSum(i, i));
		}
	}
	printf("%lld", tree.getSum(X.size() - 1, X.size() - 1));
}

Compilation message (stderr)

rail.cpp:3:20: warning: extra tokens at end of #include directive
 #include<algorithm>1
                    ^
rail.cpp: In function 'int main()':
rail.cpp:60:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = e + 1; i < X.size(); i++) {
                         ^
rail.cpp:41: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:46: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: 0 / 25
• Subtask 4: 27 / 27
• Subtask 5: 0 / 30