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 <bits/stdc++.h>
using namespace std;
struct Val {
int i, val;
};
const int M = 1 << 21, N = 2 * M, T = 500, MOD = 1e9 + 7;
int node[N];
int a[T], b[T];
vector<Val> p;
int getSum(int i) {
if(i == 1)
return 0;
int sum = getSum(i/2);
if(i % 2 == 1)
sum += node[i-1];
return sum % MOD;
}
void add(int i, int val) {
if(i == 0)
return;
node[i] = (node[i] + val) % MOD;
add(i/2, val);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int sum = 0;
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
sum += b[i] - a[i];
}
if(sum > M)
return 0;
for(int i = 0, x = 0; i < n; i++)
for(int j = b[i]; j >= a[i]; j--, x++)
p.push_back({x, j});
sort(p.begin(), p.end(),
[](Val v1, Val v2) {
return v1.val < v2.val;
});
int pre = p[0].val;
p[0].val = 1;
for(int i = 1; i < n; i++) {
bool eq = (pre != p[i].val);
pre = p[i].val;
p[i].val = p[i-1].val + eq;
}
sort(p.begin(), p.end(),
[](Val v1, Val v2) {
return v1.i < v2.i;
});
sum = 0;
for(Val v: p) {
int val = getSum(v.val + M) + 1;
add(v.val + M, val);
sum = (sum + val) % MOD;
}
cout << sum;
}
# | 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... |