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;
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define ll long long
const int N = 500010;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
pii v[N];
ll exp(int x) {
if(x==1) return 2;
if(x%2) return (2*exp(x-1))%mod;
ll aux = exp(x/2);
return (aux*aux)%mod;
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
int n,m;
cin>>n>>m;
int a,b;
for(int i=1;i<n;i++) {
cin>>a>>b;
}
for(int i=0;i<m;i++) {
cin>>v[i].F>>v[i].S;
}
sort(v,v+m);
int p=0;
int ng=0;
a=v[0].F;
b=v[0].S;
for(int i=1;i<m;i++) {
if(v[i].F<=b) {
b=v[i].S;
} else {
p+=(b-a);
a=v[i].F;
b=v[i].S;
ng++;
}
}
p+=(b-a);
ng++;
cout<<exp(n-1-p+ng)<<"\n";
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |