#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));
}
Compilation message
rail.cpp:11:24: error: '>>' should be '> >' within a nested template argument list
vector<queue<long long>> lazy;
^
rail.cpp:12:10: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
int k = 1;
^
rail.cpp: In function 'int main()':
rail.cpp:85:30: error: in C++98 'X' must be initialized by constructor, not by '{...}'
vector<long long> X = { 1,n };
^
rail.cpp:86:34: error: '>>' should be '> >' within a nested template argument list
vector<pair<long long, long long>> seg;
^
rail.cpp:90:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
seg.push_back({ s,e });
^
rail.cpp:90:24: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
seg.push_back({ s,e });
^
rail.cpp:99:7: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
for (auto segment : seg) {
^
rail.cpp:99:12: error: 'segment' does not name a type
for (auto segment : seg) {
^
rail.cpp:105:2: error: expected ';' before 'printf'
printf("%lld", tree.getSum(X.size() - 1, X.size() - 1));
^
rail.cpp:106:1: error: expected primary-expression before '}' token
}
^
rail.cpp:106:1: error: expected ')' before '}' token
rail.cpp:106:1: error: expected primary-expression before '}' token
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:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &s, &e);
^
