oj.uz

Submission #260699

# Submission time Handle Problem Language Result Execution time Memory
260699 2020-08-10T18:25:36 Z fadi57 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 28288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long

const int mx=500020;
int c[mx];
int b[mx];

vector<int>keys[mx];
int mxright[mx];
int mxleft[mx];
int n,m;
int leftt[mx];int rightt[mx];
int last[mx];
int canr(int i){
    if(leftt[mxright[i]]>=mxleft[i]&&leftt[mxright[i]]!=-1&&mxright[i]<n){
       return 1;
    }return 0;
}int canl(int i){
    if(rightt[mxleft[i]-1]<=mxright[i]&&rightt[mxleft[i]-1]!=-1&&mxleft[i]>1){
       return 1;
    }return 0;
}
int main()
{
  
  cin>>n;
  for(ll i=1;i<n;i++){
      cin>>c[i];
  }
  
  for(int i=1;i<=n;i++){
      cin>>b[i];
      for(int j=0;j<b[i];j++){
          ll x;
          cin>>x;
          keys[i].push_back(x);
      }
  }
  
    memset(last ,-1 ,sizeof last);
    
    for(int i=1;i<n;i++){
        for(int j:keys[i]){
            last[j]=i;
        }
        leftt[i]=last[c[i]];
    } 
    memset(last ,-1 ,sizeof last);
    
      for(int i=n-1;i>=1;i--){
        for(int j:keys[i+1]){
            last[j]=i+1;
        }
       rightt[i]=last[c[i]];
    }
    for(int i=1;i<=n;i++){
        
      int myr=i;
        int myl=i; mxleft[i]=i;  mxright[i]=i;
        while(1){
          int xx=0;ll xo=0;
       
          if(canr(i)){
              xx=1;
              
              myr++;
            mxright[i]=myr;
             
          }
          if(canl(i)){
              xo=1;
             
             
              myl--;  mxleft[i]=myl;
               mxleft[i]=min(mxleft[i],mxleft[mxleft[i]]);
               mxright[i]=max(mxright[i],mxright[mxleft[i]]);
        
          }
            if(xo||xx){
                
            }else{
                break;
               
            }
        } 
     
  }
  ll q;cin>>q;
  for(int i=0;i<q;i++){
      int x,y;cin>>x>>y;
     //cout<<mxleft[x]<<" "<<mxright[x];
     cout<<(mxleft[x] <= y && y <= mxright[x] ? "YES" : "NO") << '\n';
     
  }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14208 KB Output is correct
2 Correct 30 ms 14336 KB Output is correct
3 Correct 47 ms 14456 KB Output is correct
4 Correct 27 ms 14208 KB Output is correct
5 Correct 26 ms 14208 KB Output is correct
6 Correct 27 ms 14208 KB Output is correct
7 Correct 26 ms 14208 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14208 KB Output is correct
2 Correct 30 ms 14336 KB Output is correct
3 Correct 47 ms 14456 KB Output is correct
4 Correct 27 ms 14208 KB Output is correct
5 Correct 26 ms 14208 KB Output is correct
6 Correct 27 ms 14208 KB Output is correct
7 Correct 26 ms 14208 KB Output is correct
8 Correct 1467 ms 19304 KB Output is correct
9 Correct 1481 ms 19140 KB Output is correct
10 Correct 1491 ms 19292 KB Output is correct
11 Correct 1513 ms 19576 KB Output is correct
12 Correct 1447 ms 19332 KB Output is correct
13 Correct 1533 ms 19372 KB Output is correct
14 Correct 1491 ms 19276 KB Output is correct
15 Correct 1472 ms 19572 KB Output is correct
16 Correct 1430 ms 19844 KB Output is correct
17 Correct 1463 ms 19440 KB Output is correct
18 Correct 1471 ms 19448 KB Output is correct
19 Correct 1485 ms 19428 KB Output is correct
20 Correct 1462 ms 19504 KB Output is correct
21 Correct 1458 ms 19448 KB Output is correct
22 Correct 1478 ms 19436 KB Output is correct
23 Correct 1462 ms 19316 KB Output is correct
24 Correct 1458 ms 19192 KB Output is correct
25 Correct 1475 ms 19296 KB Output is correct
26 Correct 1485 ms 19112 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3037 ms 28288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14208 KB Output is correct
2 Correct 30 ms 14336 KB Output is correct
3 Correct 47 ms 14456 KB Output is correct
4 Correct 27 ms 14208 KB Output is correct
5 Correct 26 ms 14208 KB Output is correct
6 Correct 27 ms 14208 KB Output is correct
7 Correct 26 ms 14208 KB Output is correct
8 Correct 1467 ms 19304 KB Output is correct
9 Correct 1481 ms 19140 KB Output is correct
10 Correct 1491 ms 19292 KB Output is correct
11 Correct 1513 ms 19576 KB Output is correct
12 Correct 1447 ms 19332 KB Output is correct
13 Correct 1533 ms 19372 KB Output is correct
14 Correct 1491 ms 19276 KB Output is correct
15 Correct 1472 ms 19572 KB Output is correct
16 Correct 1430 ms 19844 KB Output is correct
17 Correct 1463 ms 19440 KB Output is correct
18 Correct 1471 ms 19448 KB Output is correct
19 Correct 1485 ms 19428 KB Output is correct
20 Correct 1462 ms 19504 KB Output is correct
21 Correct 1458 ms 19448 KB Output is correct
22 Correct 1478 ms 19436 KB Output is correct
23 Correct 1462 ms 19316 KB Output is correct
24 Correct 1458 ms 19192 KB Output is correct
25 Correct 1475 ms 19296 KB Output is correct
26 Correct 1485 ms 19112 KB Output is correct
27 Execution timed out 3037 ms 28288 KB Time limit exceeded
28 Halted 0 ms 0 KB -