oj.uz

Submission #219287

# Submission time Handle Problem Language Result Execution time Memory
219287 2020-04-05T03:43:41 Z dvdg6566 Port Facility (JOI17_port_facility) C++14
10 / 100
 15 ms 768 KB 
#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<ll, pi> pip;
vector<pip> V;
ll p[MAXN];
ll par(ll x){return(p[x]==x)?x:p[x]=par(p[x]);}
 
struct node{
  ll s,e,m,v;
  node *l, *r;
  node (ll _s, ll _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(ll x, ll 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);
  }
  ll query(ll x, ll 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;}
ll mem[MAXN];
 
int main(){
  cin>>N;
  for (ll i=0;i<N;++i){
    cin>>a>>b;
    V.pb(i, mp(a,b));
    p[i]=i;
  }
  sort(ALL(V), cmpa);
  M=1;
  for (ll x=0;x<SZ(V);++x){
    pi i=V[x].s;
    for (ll 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(ll i=0;i<N;++i)if (par(i) == i){
    M = (M*2);
    if (M>= MOD)assert(0);
  }
 
  root = new node(1,2*N);
 
  for(ll i=0;i<N;++i){
    // cout<<"Ask "<<V[i].s.f<<' '<<V[i].s.s<<'\n';
    ll l = root->query(V[i].s.f, V[i].s.s);
    mem[V[i].f] = l;
    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(ll i=0;i<N;++i){
    // cout<<V[i].s.f<<' '<<V[i].s.s<<'\n';
    
    ll l = root->query(V[i].s.f, V[i].s.s);
    l=abs(l);
    if (l!=INF && mem[V[i].f]!=INF){
      ll a = mem[V[i].f];
      if (a > l){
        cout<<0;
        return 0;
      }
    }
    root->up(V[i].s.f, -V[i].s.f);
  }
  cout<<M;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Runtime error 15 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Runtime error 15 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Runtime error 15 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -