Submission #427864

#	Time	Username	Problem	Language	Result	Execution time	Memory
427864		errorgorn	Port Facility (JOI17_port_facility)	C++17	78 / 100	6086 ms	423292 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline void read(int &x){
  x=0;

  char ch=getchar_unlocked();
  while (ch&16){
    x=x*10+(ch&15);
    ch=getchar_unlocked();
  }
}

const int MOD=1000000007;

int n;
ii arr[1000005];

vector<int> stk;
bool vis[1000005];
bool col[1000005];

struct node{
  vector<int> v[2000010];
  int idx[2000010];
  const int BUF=1000005;

  node (){
    memset(idx,-1,sizeof(idx));
  }

  void update(int i,int k){
    i+=BUF;

    while (i){
      v[i].pub(k);
      idx[i]++;
      i>>=1;
    }
  }

  int query(int i,int j,int k){
    i+=BUF,j+=BUF+1;

    for (;i<j;i>>=1,j>>=1){
      if (i&1){
        while (~idx[i] && vis[v[i][idx[i]]]) idx[i]--;
        if (~idx[i] && k<=arr[v[i][idx[i]]].se) return v[i][idx[i]];
        i++;
      }
      if (j&1){
        j--;
        while (~idx[j] && vis[v[j][idx[j]]]) idx[j]--;
        if (~idx[j] && k<=arr[v[j][idx[j]]].se) return v[j][idx[j]];
      }
    }

    return -1;
  }

  int query2(int i,int j,int k){
    i+=BUF,j+=BUF+1;

    for (;i<j;i>>=1,j>>=1){
      if (i&1){
        while (~idx[i] && vis[v[i][idx[i]]]) idx[i]--;
        if (~idx[i] && arr[v[i][idx[i]]].fi<=k) return v[i][idx[i]];
        i++;
      }
      if (j&1){
        j--;
        while (~idx[j] && vis[v[j][idx[j]]]) idx[j]--;
        if (~idx[j] && arr[v[j][idx[j]]].fi<=k) return v[j][idx[j]];
      }
    }

    return -1;
  }
} root= node(), root2= node();

vector<int> d1,d2;

struct node2{
  int arr[4000010];
  const int BUF=2000005;

  node2(){
    memset(arr,-1,sizeof(arr));
  }

  void update(int i,int k){
    i+=BUF;

    while (i){
      arr[i]=max(arr[i],k);
      i>>=1;
    }
  }

  int query(int i,int j){
    i+=BUF,j+=BUF+1;
    int res=-1;

    for (;i<j;i>>=1,j>>=1){
      if (i&1){
        res=max(res,arr[i]);
        i++;
      }
      if (j&1){
        j--;
        res=max(res,arr[j]);
      }
    }

    return res;
  }
} white= node2(),black= node2();

int ans=1;

int main(){
  cin.tie(0);
  cout.tie(0);
  cin.sync_with_stdio(false);

  read(n);

  rep(x,0,n){
    read(arr[x].fi),read(arr[x].se);
    d1.pub(arr[x].fi);
    d2.pub(arr[x].se);
  }

  sort(all(d1));
  sort(all(d2));


  vector<int> proc;
  rep(x,0,n) proc.pub(x);

  sort(all(proc),[](int i,int j){
    return arr[i].se<arr[j].se;
  });
  for (auto &it:proc){
    int i=lb(all(d1),arr[it].fi)-d1.begin();
    root.update(i,it);
  }

  sort(all(proc),[](int i,int j){
    return arr[i].fi>arr[j].fi;
  });
  for (auto &it:proc){
    int i=lb(all(d2),arr[it].se)-d2.begin();
    root2.update(i,it);
  }

  rep(x,0,n) if (!vis[x]){
    vis[x]=true;
    stk.pub(x);

    ans=2*ans%MOD;

    while (!stk.empty()){
      int pos=stk.back();
      stk.pob();

      //cout<<pos<<" "<<col[pos]<<endl;

      if (!col[pos]){
        white.update(arr[pos].fi,arr[pos].se);
      }
      else{
        black.update(arr[pos].fi,arr[pos].se);
      }

      int l,r;

      l=lb(all(d1),arr[pos].fi)-d1.begin();
      r=ub(all(d1),arr[pos].se)-d1.begin()-1;
      while (true){
        int it=root.query(l,r,arr[pos].se);
        if (it==-1) break;

        vis[it]=true;
        stk.pub(it);

        col[it]=!col[pos];
      }

      l=lb(all(d2),arr[pos].fi)-d2.begin();
      r=ub(all(d2),arr[pos].se)-d2.begin()-1;
      while (true){
        int it=root2.query2(l,r,arr[pos].fi);
        if (it==-1) break;

        vis[it]=true;
        stk.pub(it);

        col[it]=!col[pos];
      }
    }
  }

  rep(x,0,n){
    if (!col[x]){ //white
      if (white.query(arr[x].fi,arr[x].se)>arr[x].se) ans=0;
    }
    else{ //black
      if (black.query(arr[x].fi,arr[x].se)>arr[x].se) ans=0;
    }
  }

  cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22