Submission #4272331

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define N 2000010
#define mod 1000000007
ll nxt[N],n;
P d[N];
vector<ll> g[N];
void make_edge(ll a,ll b){
  //cout<<"edge:"<<a<<" "<<b<<endl;
  g[a].push_back(b);
  g[b].push_back(a);
}
ll vis[N];
bool dfs(ll x,ll col){
  if(~vis[x]){
    return vis[x]==col;
  }
  vis[x]=col;
  for(auto y:g[x]){
    if(dfs(y,1^col)==0)return 0;
  }
  return 1;
}
bool solve(){
  stack<ll> s[2];
  vector<P> v;
  for(int i=0;i<n;i++){
    v.push_back(make_pair(d[i].first,i*2+0));
    v.push_back(make_pair(d[i].second,i*2+1));
  }sort(v.begin(),v.end());
  for(int i=0;i<2*n;i++){
    ll id=v[i].second/2,type=v[i].second%2;
    ll col=vis[d[id].second];
    if(type==0)s[col].push(id);
    if(type==1){
      if(s[col].top()!=id)return 0;
      s[col].pop();
    }
  }
  return 1;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++)scanf("%lld%lld",&d[i].first,&d[i].second);
  sort(d,d+n);
  for(int i=1;i<=2*n;i++)nxt[i]=1e15;
  priority_queue<ll,vector<ll>,greater<ll> > Q;
  set<ll> S; S.insert(-1); S.insert(1e15);
  vector<bool> used(2*N,0);
  for(int i=0;i<n;i++){
    ll a=d[i].first,b=d[i].second;
    S.insert(b);
    while(!Q.empty()){
      ll x=Q.top();
      if(x>a)break;
      Q.pop();
      if(used[x])continue; used[x]=1;
      if(nxt[x]<1e15)Q.push(nxt[x]);
    }
    vector<ll> united; united.clear();
    while(!Q.empty()){
      ll x=Q.top();
      if(x>b)break;
      Q.pop();
      united.push_back(x);
    }
    ll siz=united.size();
    if(siz==0){
      Q.push(b);
      continue;
    }
    Q.push(united[0]);
    auto ir=S.lower_bound(b); ir--;
    nxt[b]=nxt[*ir];
    united.push_back(b);
    for(int j=1;j<=siz;j++){
      auto it=S.lower_bound(united[j]); it--;
      if(*it!=-1)nxt[*it]=united[j];
    }
    
    for(int j=0;j<siz;j++){
      make_edge(united[j],b);
    }
  }
  
  for(int i=0;i<n;i++){
    vis[d[i].first]=0;
    vis[d[i].second]=-1;
  }
  
  ll ans=1;
  for(int i=1;i<=2*n;i++){
    if(~vis[i])continue;
    (ans*=2)%=mod;
    ans*=dfs(i,0);
  }
  cout<<ans*solve()<<endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<n;i++)scanf("%lld%lld",&d[i].first,&d[i].second);
                                                                 ^

Judge Result