Submission #260710

#	Time	Username	Problem	Language	Result	Execution time	Memory
260710		fadi57	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3076 ms	24128 KiB

long_mansion

#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()
{
  
 scanf("%d",&n);
  for(ll i=1;i<n;i++){
       scanf("%d",&c[i]);
  }
  
  for(int i=1;i<=n;i++){
      scanf("%d",&b[i]);
      for(int j=0;j<b[i];j++){
          int x;
           scanf("%d",&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(canl(i)){
              xo=1;
             
             
              myl--;  mxleft[i]=myl;
               mxleft[i]=min(mxleft[i],mxleft[mxleft[i]]);
               mxright[i]=max(mxright[i],mxright[mxleft[i]]);
        
          }else if(canr(i)){
              xx=1;
              
              myr++;
            mxright[i]=myr;
             
          }else {break;}
           
        } 
     
  }
  int q;cin>>q;
  for(int i=0;i<q;i++){
      int x,y; scanf("%d%d",&x,&y); 
     //cout<<mxleft[x]<<" "<<mxright[x];
     printf(mxleft[x] <= y && y <= mxright[x] ? "YES\n" : "NO\n") <<'\n';
     
  }

}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:64:15: warning: variable 'xx' set but not used [-Wunused-but-set-variable]
           int xx=0;ll xo=0;
               ^~
long_mansion.cpp:64:23: warning: variable 'xo' set but not used [-Wunused-but-set-variable]
           int xx=0;ll xo=0;
                       ^~
long_mansion.cpp:88:67: warning: value computed is not used [-Wunused-value]
      printf(mxleft[x] <= y && y <= mxright[x] ? "YES\n" : "NO\n") <<'\n';
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
long_mansion.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
long_mansion.cpp:31:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d",&c[i]);
        ~~~~~^~~~~~~~~~~~
long_mansion.cpp:35:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&b[i]);
       ~~~~~^~~~~~~~~~~~
long_mansion.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
            scanf("%d",&x);
            ~~~~~^~~~~~~~~
long_mansion.cpp:86:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int x,y; scanf("%d%d",&x,&y); 
                ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75