Submission #218993

#	Time	Username	Problem	Language	Result	Execution time	Memory
218993		dvdg6566	Port Facility (JOI17_port_facility)	C++14	10 / 100	6065 ms	384 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MOD = 1e9+7;
const ll INF = 1e10;
const ll MAXN = 300100;

stack<pi> S;
int N,M,a,b;
vpi V;
vpi safe;
int fw[MAXN];
int p[MAXN];
int par(int x){return(p[x]==x)?x:p[x]=par(p[x]);}

void up(int x, int v){
  for (;x<MAXN;x+=x&(-x))fw[x]+=v;
}
int query(int x){
  int res=0;
  for(;x;x-=x&(-x))res+=fw[x];
  return res;
}
int rmq(int a, int b){
  return query(b) - query(a-1);
}

int main(){
  cin>>N;
  for (int i=0;i<N;++i){
    cin>>a>>b;
    V.pb(a,b);
    p[i]=i;
  }
  sort(ALL(V));
  M=1;
  for (int x=0;x<SZ(V);++x){
    pi i=V[x];
    int safe=1;
    for (int y=0;y<SZ(V);++y){
      pi j=V[y];
      if (j.f<i.f&&j.s>i.f&&j.s<i.s){
        p[par(x)] = par(y);
        // cout<<x<<' '<<y<<'\n';
      }
    }
  }
  for(int i=0;i<N;++i)if (par(i) == i){
    M = (M*2)%MOD;
  }
  // for (auto i : V){
  //   int x=rmq(i.f,i.s);
  //   if (x==0)M=(M*2)%MOD;
  //   int a=i.f;
  //   int b=i.s;
  //   up(a,1);
  //   up(b,-1);
  // }

  for (auto i : V)for (auto j:V)for (auto k:V){
    if (i.f<j.f && j.f<k.f && i.s<j.s && j.s<k.s && i.s>k.f){
      cout<<0;
      return 0;
    }
  }
  cout<<M;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:51:9: warning: unused variable 'safe' [-Wunused-variable]
     int safe=1;
         ^~~~

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