#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef pair<int, int> pii;
const int N=1<<10;
bool czy=1;
pii seg[N];
vector<int> tab[N+N], tab2[N+N];
//int opt[3][N+N], opt2[3][N+N];
void insert(int id){
int l=seg[id].st+N, r=seg[id].nd+1+N;
for(;l<r; l>>=1, r>>=1){
if(l&1)tab[l++].push_back(id);
if(r&1)tab[--r].push_back(id);
}
}
int vis[N];
void dfs(int s){
vector<int> V;
V.push_back(s);
vis[s]=1;
for(int i=0; i<V.size(); i++){
int v=V[i];
int l=seg[v].st+N, r=seg[v].nd+N;
//cout<<v<<" "<<vis[v]<<"\n";
while(l){
while(tab[l].size()){
int u=tab[l].back();
//cout<<l<<" "<<v<<" "<<u<<"\n";
if(seg[u].nd>seg[v].nd)break;
if(!vis[u]){
vis[u]=3-vis[v];
V.push_back(u);
}
else if(vis[u]==vis[v])czy=0;
tab[l].pop_back();
}
l/=2;
}
while(r){
while(tab2[r].size()){
int u=tab2[r].back();
//cout<<r<<" "<<v<<" + "<<u<<"\n";
if(seg[u].st<seg[v].st)break;
if(!vis[u]){
vis[u]=3-vis[v];
V.push_back(u);
}
else if(vis[u]==vis[v])czy=0;
tab2[r].pop_back();
}
r/=2;
}
}
}
//int lew[N], pra[N];
bool solve(vector<int> id){
vector<pair<int, pii> > V;
for(int i:id){
V.push_back({seg[i].st, {1, i}});
V.push_back({seg[i].nd, {-1, i}});
}
vector<int> V2;
sort(V.begin(), V.end());
for(int i=0; i<V.size(); i++){
if(V[i].nd.st==1)V2.push_back(V[i].nd.nd);
else{
if(!V2.size() || V2.back()!=V[i].nd.nd)return 0;
V2.pop_back();
}
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
for(int i=0; i<n; i++){
cin>>seg[i].st>>seg[i].nd;
insert(i);
}
for(int i=1; i<N+N; i++){
sort(tab[i].begin(), tab[i].end(), [](int a, int b){return seg[a].nd>seg[b].nd;});
tab2[i]=tab[i];
sort(tab2[i].begin(), tab2[i].end(), [](int a, int b){return seg[a].st<seg[b].st;});
//cout<<i<<"a\n";
//for(int j:tab[i])cout<<j<<" ";
//cout<<"\n";
}
int ile=0, ans=1;
int mod=1e9+7;
/*vector<pii> V2;
for(int i=0; i<n; i++){
V2.push_back({seg[i].st-seg[i].nd, i});
}
sort(V2.begin(), V2.end());*/
for(int i=0; i<n; i++){
int j=i;
if(!vis[j]){
ile++;
ans*=2;
if(ans>=mod)ans-=mod;
dfs(j);
}
}
vector<int> V, V2;
for(int i=0; i<n; i++){
if(vis[i]==2)V.push_back(i);
else V2.push_back(i);
}
czy=solve(V)&solve(V2);
/*vector<pair<pii, int> > V;
for(int i=0; i<n; i++){
V.push_back({seg[i], i});
}
sort(V.begin(), V.end());
set<int> S;
for(int i=0; i<n; i++){
int a=V[i].st.st, b=V[i].st.nd, c=V[i].nd;
S.insert(b);
auto it=S.find(b);
if(it!=S.begin()){
it--;
lew[c]=*it;
}
else lew[c]=a;
}
S.clear();
for(int i=0; i<n; i++)swap(V[i].st.st, V[i].st.nd);
sort(V.begin(), V.end());
for(int i=n-1; i>=0; i--){
int a=V[i].st.st, b=V[i].st.nd, c=V[i].nd;
//cerr<<a<<" "<<b<<" "<<c<<endl;
S.insert(b);
auto it=S.find(b);
it++;
if(b!=(*S.crend())){
pra[c]=*it;
}
else pra[c]=a;
}
for(int i=0; i<n; i++){
//cerr<<pra[i]<<" "<<lew[i]<<endl;
if(pra[i]<lew[i])ans=0;
}*/
cout<<ans*czy;
}
Compilation message
sparklers.cpp: In function 'void dfs(int)':
sparklers.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
sparklers.cpp: In function 'bool solve(std::vector<int>)':
sparklers.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
