oj.uz

Submission #431506

# Submission time Handle Problem Language Result Execution time Memory
431506 2021-06-17T12:27:28 Z kai824 Long Mansion (JOI17_long_mansion) C++17
100 / 100
 723 ms 146220 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define f first
#define s second
#define mp make_pair

int last[500005],L[500005],R[500005];
int c[500005];
vector<int> v[500005];
pii rng[500005];//range...

void aq(){//to be kept for later...
  int q,a,b;
  cin>>q;
  while(q--){
    cin>>a>>b;
    a--;b--;
    if(rng[a].f<=b && b<=rng[a].s){
      cout<<"YES\n";
    }else cout<<"NO\n";
  }
}

int n;
struct st{
  int s,e;
  int ll,rr;
  st *l,*r;
  st(int ss,int ee){
    s=ss;e=ee;
    if(s==e){
      l=r=NULL;
      ll=L[s];
      rr=R[s];
    }else{
      l=new st(s,(s+e)/2);
      r=new st((s+e)/2+1,e);
      ll=min(l->ll,r->ll);
      rr=max(l->rr,r->rr);
    }
  }
  int lsearch(int start,int limit){
    if(start<s)return start;
    if(start<e){
      int ans=-1;
      if((s+e)/2<start){
        ans=r->lsearch(start,limit);
        if(ans==-1)return l->lsearch(start,limit);
        return ans;
      }
      return l->lsearch(start,limit);
    }
    //includes whole range:
    if(rr<=limit)return -1;
    if(s==e)return s;
    if(r->rr<=limit)return l->lsearch(start,limit);
    else return r->lsearch(start,limit);
  }
  int rsearch(int start,int limit){
    if(e<start)return start;
    if(s<start){
      int ans=n-1;
      if(start<=(s+e)/2){
        ans=l->rsearch(start,limit);
        if(ans==n-1)return r->rsearch(start,limit);
        return ans;
      }
      return r->rsearch(start,limit);
    }
    //includes whole range
    if(ll>=limit)return n-1;
    if(s==e)return s;
    if(l->ll>=limit)return r->rsearch(start,limit);
    else return l->rsearch(start,limit);
  }
} *nx;

struct node{
  int mn=1e9,mx=-1;
  int s,e;
  node *l,*r;
  node(int ss,int ee){
    s=ss;e=ee;
    if(s==e){
      l=r=NULL;
    }else{
      l=new node(s,(s+e)/2);
      r=new node((s+e)/2+1,e);
    }
  }
  void upd(int p){
    mn=min(mn,rng[p].f);
    mx=max(mx,rng[p].s);
    if(s==e){
      return;
    }
    if(p<=(s+e)/2)l->upd(p);
    else r->upd(p);
  }
  pii query(int a,int b){
    if(a<=s && e<=b)return mp(mn,mx);
    pii ans=mp(1e9,-1),tmp;
    if(a<=(s+e)/2){
      ans=l->query(a,b);
    }
    if((s+e)/2<b){
      tmp=r->query(a,b);
      ans.f=min(ans.f,tmp.f);
      ans.s=max(ans.s,tmp.s);
    }
    return ans;
  }
} *root;

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int a;
  cin>>n;
  for(int i=0;i+1<n;i++){
    cin>>c[i];
  }
  for(int i=0;i<n;i++){
    cin>>a;
    v[i].resize(a);
    for(int j=0;j<a;j++){
      cin>>v[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    last[i]=-1;
  }
  for(int i=0;i+1<n;i++){//L[node]: nearest left node of same key...
    for(int x:v[i]){
      last[x]=i;
    }
    L[i]=last[c[i]];
  }
  for(int i=1;i<=n;i++)last[i]=1e9;
  for(int i=n-2;i>=0;i--){
    for(int x:v[i+1]){
      last[x]=i+1;
    }
    R[i]=last[c[i]];
  }

  root=new node(0,n-1);nx=new st(0,n-2);

  for(int i=0;i<n;i++){
    rng[i].f=rng[i].s=i;
    while(true){
      pii tmp=rng[i];
      // while(rng[i].f>0 && R[rng[i].f-1]<=rng[i].s)rng[i].f--;
      rng[i].f=nx->lsearch(rng[i].f-1,rng[i].s)+1;//expand left: first index where R[i]>rng[i].s
      rng[i].s=nx->rsearch(rng[i].s,rng[i].f);//expand right: first index where L[i]<rng[i].f
      // while(rng[i].s+1<n && L[rng[i].s]>=rng[i].f)rng[i].s++;

      if(tmp==rng[i])break;

      //fast expansion for hopefully amortized O(n log n)?
      tmp=root->query(rng[i].f,i);
      rng[i].f=min(rng[i].f,tmp.f);
      rng[i].s=max(rng[i].s,tmp.s);
    }
    root->upd(i);
    // cout<<i<<' '<<rng[i].f<<' '<<rng[i].s<<'\t'<<L[i]<<' '<<R[i]<<'\n';
  }

  aq();
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12652 KB Output is correct
2 Correct 13 ms 12876 KB Output is correct
3 Correct 15 ms 13304 KB Output is correct
4 Correct 12 ms 12656 KB Output is correct
5 Correct 12 ms 12552 KB Output is correct
6 Correct 12 ms 12600 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12652 KB Output is correct
2 Correct 13 ms 12876 KB Output is correct
3 Correct 15 ms 13304 KB Output is correct
4 Correct 12 ms 12656 KB Output is correct
5 Correct 12 ms 12552 KB Output is correct
6 Correct 12 ms 12600 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct
8 Correct 137 ms 14156 KB Output is correct
9 Correct 124 ms 14160 KB Output is correct
10 Correct 136 ms 14556 KB Output is correct
11 Correct 154 ms 15120 KB Output is correct
12 Correct 129 ms 14196 KB Output is correct
13 Correct 130 ms 14460 KB Output is correct
14 Correct 127 ms 14360 KB Output is correct
15 Correct 132 ms 14536 KB Output is correct
16 Correct 138 ms 14672 KB Output is correct
17 Correct 121 ms 14344 KB Output is correct
18 Correct 129 ms 14392 KB Output is correct
19 Correct 123 ms 14440 KB Output is correct
20 Correct 119 ms 14588 KB Output is correct
21 Correct 147 ms 14648 KB Output is correct
22 Correct 143 ms 14476 KB Output is correct
23 Correct 127 ms 14224 KB Output is correct
24 Correct 139 ms 14220 KB Output is correct
25 Correct 136 ms 14276 KB Output is correct
26 Correct 132 ms 14192 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 38320 KB Output is correct
2 Correct 274 ms 38036 KB Output is correct
3 Correct 271 ms 43664 KB Output is correct
4 Correct 260 ms 45288 KB Output is correct
5 Correct 306 ms 45248 KB Output is correct
6 Correct 277 ms 44520 KB Output is correct
7 Correct 265 ms 44328 KB Output is correct
8 Correct 270 ms 44296 KB Output is correct
9 Correct 305 ms 44352 KB Output is correct
10 Correct 314 ms 44276 KB Output is correct
11 Correct 302 ms 44316 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12652 KB Output is correct
2 Correct 13 ms 12876 KB Output is correct
3 Correct 15 ms 13304 KB Output is correct
4 Correct 12 ms 12656 KB Output is correct
5 Correct 12 ms 12552 KB Output is correct
6 Correct 12 ms 12600 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct
8 Correct 137 ms 14156 KB Output is correct
9 Correct 124 ms 14160 KB Output is correct
10 Correct 136 ms 14556 KB Output is correct
11 Correct 154 ms 15120 KB Output is correct
12 Correct 129 ms 14196 KB Output is correct
13 Correct 130 ms 14460 KB Output is correct
14 Correct 127 ms 14360 KB Output is correct
15 Correct 132 ms 14536 KB Output is correct
16 Correct 138 ms 14672 KB Output is correct
17 Correct 121 ms 14344 KB Output is correct
18 Correct 129 ms 14392 KB Output is correct
19 Correct 123 ms 14440 KB Output is correct
20 Correct 119 ms 14588 KB Output is correct
21 Correct 147 ms 14648 KB Output is correct
22 Correct 143 ms 14476 KB Output is correct
23 Correct 127 ms 14224 KB Output is correct
24 Correct 139 ms 14220 KB Output is correct
25 Correct 136 ms 14276 KB Output is correct
26 Correct 132 ms 14192 KB Output is correct
27 Correct 268 ms 38320 KB Output is correct
28 Correct 274 ms 38036 KB Output is correct
29 Correct 271 ms 43664 KB Output is correct
30 Correct 260 ms 45288 KB Output is correct
31 Correct 306 ms 45248 KB Output is correct
32 Correct 277 ms 44520 KB Output is correct
33 Correct 265 ms 44328 KB Output is correct
34 Correct 270 ms 44296 KB Output is correct
35 Correct 305 ms 44352 KB Output is correct
36 Correct 314 ms 44276 KB Output is correct
37 Correct 302 ms 44316 KB Output is correct
38 Correct 551 ms 122272 KB Output is correct
39 Correct 585 ms 146220 KB Output is correct
40 Correct 483 ms 96924 KB Output is correct
41 Correct 723 ms 144728 KB Output is correct
42 Correct 270 ms 45524 KB Output is correct
43 Correct 265 ms 45512 KB Output is correct
44 Correct 419 ms 72340 KB Output is correct
45 Correct 480 ms 72620 KB Output is correct
46 Correct 433 ms 72612 KB Output is correct
47 Correct 252 ms 45584 KB Output is correct
48 Correct 270 ms 45332 KB Output is correct
49 Correct 480 ms 72356 KB Output is correct
50 Correct 604 ms 72464 KB Output is correct
51 Correct 436 ms 72708 KB Output is correct
52 Correct 429 ms 71320 KB Output is correct
53 Correct 589 ms 97252 KB Output is correct
54 Correct 697 ms 123236 KB Output is correct
55 Correct 526 ms 97472 KB Output is correct