이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = a; i < a; ++i)
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 1000100
#define NN 1111
#define taskname ""
using namespace std;
int n, a[N], b[N];
const long long MOD = 1e9 + 7;
long long BIT[N];
long long Get(int u) {
long long ans = 0;
for (; u > 0 ; u -= u & -u) ans = (ans + BIT[u]) % MOD;
return ans;
}
void Up(int u, long long val) {
for (; u < N; u += u & -u) BIT[u] = (BIT[u] + val) % MOD;
}
vector<int> e;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
FOR(i, 1, n) {
cin >> a[i] >> b[i];
FOR(j, a[i], b[i]) e.push_back(j);
}
e.push_back(0);
sort(e.begin(), e.end());
e.resize(unique(e.begin(), e.end()) - e.begin());
Up(1, 1);
long long ans = 0;
FOR(i, 1, n) {
FORD(k, b[i], a[i]) {
int p = lower_bound(e.begin(), e.end(), k) - e.begin() + 1;
long long now = Get(p - 1);
Up(p, now);
ans = (ans + now) % MOD;
}
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |