| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 20546 | CodingAmolang (#35) | 초음속철도 (OJUZ11_rail) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using std::queue;
using std::vector;
const long long MOD = 1000000007;
struct segment_tree {
vector<long long> tree;
vector<queue<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);
}
void update_lazy(int node, int start, int end) {
std::queue<long long>& que = lazy[node];
while (!que.empty()) {
long long 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, long long 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;
}
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);
}
};
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(0,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,e, tree.getSum(s, e));
tree.update(e + 1, X.size() - 1, -1);
}
printf("%lld", tree.getSum(X.size() - 1, X.size() - 1));
}