Submission #218970

#	Time	Username	Problem	Language	Result	Execution time	Memory
218970		dvdg6566	Port Facility (JOI17_port_facility)	C++14	0 / 100	4 ms	256 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];

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);
  }
  sort(ALL(V));
  M=1;
  for (auto i:V){
    int safe=1;
    for (auto j:V){
      if (j.f<i.f&&j.s>i.f&&j.s<i.s)safe=0;
    }
    if (safe)M*=2;
  }
  // 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;
      assert(0);
      return 0;
    }
  }
  cout<<M;
}

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