Submission #219104

#	Time	Username	Problem	Language	Result	Execution time	Memory
219104		dvdg6566	Port Facility (JOI17_port_facility)	C++14	10 / 100	18 ms	2176 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 = 1e9;
const ll MAXN = 300100;
 
stack<pi> S;
ll N,M,a,b;
typedef pair<int, pi> pip;
vector<pip> V;
vpi safe;
 
int p[MAXN];
int par(int x){return(p[x]==x)?x:p[x]=par(p[x]);}
 
struct node{
  int s,e,m,v;
  node *l, *r;
  node (int _s, int _e):s(_s), e(_e){
    m=(s+e)/2;v=-INF;
    if (s!=e){
      l=new node(s,m);
      r=new node(m+1,e);
    }
  }
  void up(int x, int val){
    if (s==e){v=val;return;}
    if (x<=m)l->up(x,val);
    else r->up(x,val);
    v=max(l->v,r->v);
  }
  int query(int x, int y){
    // cout<<x<<' '<<y<<' '<<s<<' '<<e<<'\n';
    if (s==x&&e==y)return v;
    if (y <= m)return l->query(x,y);
    else if (x>m)return r->query(x,y);
    return max(l->query(x,m), r->query(m+1,y));
  }
}*root;
 
bool cmpa(pip x, pip y){return x.s.f<y.s.f;}
bool cmpb(pip x, pip y){return x.s.s>y.s.s;}
int mem[MAXN];
 
int main(){
  cin>>N;
  for (int i=0;i<N;++i){
    cin>>a>>b;
    V.pb(i, mp(a,b));
    p[i]=i;
  }
  sort(ALL(V), cmpa);
  M=1;
  for (int x=0;x<SZ(V);++x){
    pi i=V[x].s;
    int safe=1;
    for (int y=0;y<SZ(V);++y){
      pi j=V[y].s;
      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;
  }
 
  root = new node(1,2*N);
 
  for(int i=0;i<N;++i){
    // cout<<"Ask "<<V[i].s.f<<' '<<V[i].s.s<<'\n';
    int l = root->query(V[i].s.f, V[i].s.s);
    if (l!=-INF){
      mem[V[i].f] = l;
      assert(l!=0);
      // cout<<"Storing "<<V[i].s.f<<' '<<V[i].s.s<<' '<<l<<'\n'; 
    }
    root->up(V[i].s.s, V[i].s.s);
    // cout<<"Up "<<V[i].s.s<<'\n';
  }
 
  root = new node(1,2*N);
  sort(ALL(V), cmpb);
 
  for(int i=0;i<N;++i){
    // cout<<V[i].s.f<<' '<<V[i].s.s<<'\n';
    
    int l = root->query(V[i].s.f, V[i].s.s);
    l=abs(l);
    if (l!=-INF && mem[V[i].f]!=INF){
      int a = mem[V[i].f];
      if (a > l){
        if (N>20)assert(0);
        cout<<0;
        return 0;
      }
    }
    root->up(V[i].s.f, -V[i].s.f);
  }
  cout<<M;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:69: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