#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct node
{
pii max_ = {-1e9,0};
pii min_ = {1e9,0};
node operator+(const node& other)
{
node res;
res.max_ = max(max_,other.max_);
res.min_ = min(min_,other.min_);
return res;
}
};
const int tree_siz = 2048*2048-1;
node drzewo[tree_siz+1];
node get_seg(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return {{-1e9,0},{1e9,0}};
if(p1 >= s1 && p2 <= s2) return drzewo[akt];
return get_seg(akt*2,p1,(p1+p2)/2,s1,s2)+get_seg(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}
void upd(int v)
{
drzewo[v] = drzewo[v*2] + drzewo[v*2+1];
if(v != 1) upd(v/2);
}
void change(int l, int r, int ind, bool w = 0)
{
if(!w)
{
drzewo[tree_siz/2+1+l] = {{r,ind},{1e9,ind}};
drzewo[tree_siz/2+1+r] = {{-1e9,ind},{l,ind}};
}
else
{
drzewo[tree_siz/2+1+l] = {{-1e9,ind},{1e9,ind}};
drzewo[tree_siz/2+1+r] = {{-1e9,ind},{1e9,ind}};
}
upd((tree_siz/2+1+l)/2);
upd((tree_siz/2+1+r)/2);
}
int L[1000'001];
int R[1000'001];
int ans[1000'001];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n;
cin >> n;
rep(i,n)
{
cin >> L[i] >> R[i];
ans[i] = -1;
change(L[i],R[i],i);
}
ll ways = 1;
rep(i,n)
{
if(ans[i] == -1)
{
ways *= 2;
ways %= MOD;
ans[i] = 0;
change(L[i],R[i],i,1);
queue<int> q;
q.push(i);
while(!q.empty())
{
int t = q.front();
q.pop();
node seg = get_seg(1,0,tree_siz/2,L[t],R[t]);
while(seg.max_.ff > R[t] || seg.min_.ff < L[t])
{
int ind = seg.max_.ss;
if(seg.min_.ff < L[t])
{
ind = seg.min_.ss;
}
ans[ind] = ans[t] ^ 1;
change(L[ind],R[ind],ind,1);
seg = get_seg(1,0,tree_siz/2,L[t],R[t]);
q.push(ind);
}
}
}
}
vector<pii> sort_vert;
rep(i,n) sort_vert.pb({L[i],i});
sort(all(sort_vert));
stack<int> st[2];
forall(it,sort_vert)
{
int v = it.ss;
int b = ans[v];
while(siz(st[b]) > 0 && R[st[b].top()] < L[v])
{
st[b].pop();
}
if(siz(st[b]) != 0 && R[st[b].top()] < R[v])
{
cout << "0\n";
return 0;
}
st[b].push(v);
}
cout << ways << "\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... |