oj.uz

Submission #431375

# Submission time Handle Problem Language Result Execution time Memory
431375 2021-06-17T11:27:12 Z kai824 Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 26400 KB 
#include<bits/stdc++.h>
using namespace std;

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

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";
  }
}
int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int n,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]];
  }

  for(int i=0;i<n;i++){
    rng[i].f=rng[i].s=i;
    while(true){
      bool br=true;
      while(rng[i].f>0 && r[rng[i].f-1]<=rng[i].s)rng[i].f--,br=false;
      while(rng[i].s+1<n && l[rng[i].s]>=rng[i].f)rng[i].s++,br=false;
      if(br)break;
    }
  }

  aq();
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 17 ms 12260 KB Output is correct
3 Correct 24 ms 12364 KB Output is correct
4 Correct 13 ms 12108 KB Output is correct
5 Correct 14 ms 12204 KB Output is correct
6 Correct 11 ms 12212 KB Output is correct
7 Correct 14 ms 12108 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 17 ms 12260 KB Output is correct
3 Correct 24 ms 12364 KB Output is correct
4 Correct 13 ms 12108 KB Output is correct
5 Correct 14 ms 12204 KB Output is correct
6 Correct 11 ms 12212 KB Output is correct
7 Correct 14 ms 12108 KB Output is correct
8 Correct 139 ms 13732 KB Output is correct
9 Correct 138 ms 13620 KB Output is correct
10 Correct 132 ms 13932 KB Output is correct
11 Correct 180 ms 14020 KB Output is correct
12 Correct 117 ms 13892 KB Output is correct
13 Correct 141 ms 13872 KB Output is correct
14 Correct 127 ms 13832 KB Output is correct
15 Correct 123 ms 13924 KB Output is correct
16 Correct 138 ms 14136 KB Output is correct
17 Correct 141 ms 13884 KB Output is correct
18 Correct 141 ms 13928 KB Output is correct
19 Correct 144 ms 13880 KB Output is correct
20 Correct 137 ms 14004 KB Output is correct
21 Correct 130 ms 14092 KB Output is correct
22 Correct 129 ms 13876 KB Output is correct
23 Correct 131 ms 13760 KB Output is correct
24 Correct 149 ms 13764 KB Output is correct
25 Correct 129 ms 13716 KB Output is correct
26 Correct 143 ms 13792 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 24760 KB Output is correct
2 Correct 2037 ms 26400 KB Output is correct
3 Execution timed out 3072 ms 18708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12236 KB Output is correct
2 Correct 17 ms 12260 KB Output is correct
3 Correct 24 ms 12364 KB Output is correct
4 Correct 13 ms 12108 KB Output is correct
5 Correct 14 ms 12204 KB Output is correct
6 Correct 11 ms 12212 KB Output is correct
7 Correct 14 ms 12108 KB Output is correct
8 Correct 139 ms 13732 KB Output is correct
9 Correct 138 ms 13620 KB Output is correct
10 Correct 132 ms 13932 KB Output is correct
11 Correct 180 ms 14020 KB Output is correct
12 Correct 117 ms 13892 KB Output is correct
13 Correct 141 ms 13872 KB Output is correct
14 Correct 127 ms 13832 KB Output is correct
15 Correct 123 ms 13924 KB Output is correct
16 Correct 138 ms 14136 KB Output is correct
17 Correct 141 ms 13884 KB Output is correct
18 Correct 141 ms 13928 KB Output is correct
19 Correct 144 ms 13880 KB Output is correct
20 Correct 137 ms 14004 KB Output is correct
21 Correct 130 ms 14092 KB Output is correct
22 Correct 129 ms 13876 KB Output is correct
23 Correct 131 ms 13760 KB Output is correct
24 Correct 149 ms 13764 KB Output is correct
25 Correct 129 ms 13716 KB Output is correct
26 Correct 143 ms 13792 KB Output is correct
27 Correct 1064 ms 24760 KB Output is correct
28 Correct 2037 ms 26400 KB Output is correct
29 Execution timed out 3072 ms 18708 KB Time limit exceeded
30 Halted 0 ms 0 KB -