fork download
copy 
  1. // fan Le Minh Nhat 30 nam
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define PRL "BOOL"
  9. #define pb push_back
  10. #define MASK(x) 1LL << x
  11. #define fre(PRL) freopen(PRL".inp","r",stdin)
  12. #define fro(PRL) freopen(PRL".out","w",stdout)
  13.  
  14. typedef pair<ll,int>ii;
  15. typedef pair<int,ii>iii;
  16.  
  17. const int MOD = 1e9+7;
  18. const ll INF = 1e12+7;
  19. const int Maxn = 1e5+7;
  20. const int di[]={0,0,1,-1};
  21. const int dj[]={-1,1,0,0};
  22.  
  23. string a[Maxn];
  24. int pre[Maxn],suff[Maxn],r[Maxn],l[Maxn],f[Maxn],x[Maxn],y[Maxn];
  25. void run_case(){
  26.     int n,q;
  27.     cin>>n>>q;
  28.     a[0]="or";
  29.     a[n+1]="or";
  30.     f[0]=0;
  31.     for(int i=1;i<=n;i++){
  32.         cin>>a[i];
  33.         f[i]=f[i-1]+(a[i]=="false"? 1:0);
  34.     }
  35.     x[0]=0;
  36.     for(int i=1;i<=n;i++){
  37.         if (a[i]=="or") x[i]=i;
  38.         else x[i]=x[i-1];
  39.     }
  40.     y[n+1]=n+1;
  41.     for(int i=n;i>=1;i--){
  42.         if (a[i]=="or") y[i]=i;
  43.         else y[i]=y[i+1];
  44.     }
  45.     if (a[1]=="true") pre[1]=1;
  46.     else pre[1]=0;
  47.     for(int i=2;i<=n;i+=2){
  48.         if (a[i]=="or"){
  49.             if (a[i+1]=="true") pre[i+1]=1;
  50.             else pre[i+1]=0;
  51.         }
  52.         else{
  53.             if (pre[i-1]==0) pre[i+1]=0;
  54.             else{
  55.                 if (a[i+1]=="true") pre[i+1]=1;
  56.                 else pre[i+1]=0;
  57.             }
  58.         }
  59.     }
  60.     //
  61.     if (a[n]=="true") suff[n]=1;
  62.     else suff[n]=0;
  63.     for(int i=n-1;i>=1;i-=2){
  64.         if (a[i]=="or"){
  65.             if (a[i-1]=="true") suff[i-1]=1;
  66.             else suff[i-1]=0;
  67.         }
  68.         else{
  69.             if (suff[i+1]==0) suff[i-1]=0;
  70.             else{
  71.                 if (a[i-1]=="true") suff[i-1]=1;
  72.                 else suff[i-1]=0;
  73.             }
  74.         }
  75.     }
  76.     memset(l,0,sizeof(l));
  77.     memset(r,0,sizeof(r));
  78.     for(int i=2;i<=n;i++){
  79.         if (a[i]=="or"){
  80.             if (pre[i-1]==1) l[i]=l[i-1]+1;
  81.             else l[i]=l[i-1];
  82.         }
  83.         else l[i]=l[i-1];
  84.     }
  85.     for(int i=n-1;i>=1;i--){
  86.         if (a[i]=="or"){
  87.             if (suff[i+1]==1) r[i]=r[i+1]+1;
  88.             else r[i]=r[i+1];
  89.         }
  90.         else r[i]=r[i+1];
  91.     }
  92.     while(q--){
  93.         int u,v;
  94.         string s;
  95.         cin>>u>>v>>s;
  96.         if (s=="true"){
  97.             if (l[u-1]>0 || r[v+1]>0) cout<<"Y";
  98.             else{
  99.                 int left=x[u],right=y[v];
  100.                 if (f[u-1]-f[left]==0 && f[right-1]-f[v]==0) cout<<"Y";
  101.                 else cout<<"N";
  102.             }
  103.         }
  104.         else{
  105.             if (l[u-1]>0 || r[v+1]>0) cout<<"N";
  106.             else cout<<"Y";
  107.         }
  108.     }
  109. }
  110. int main(){
  111.     ios_base::sync_with_stdio(false);
  112.     cout.tie(0);
  113.     if (fopen(PRL ".inp", "r"))
  114.     {
  115.         freopen(PRL ".inp", "r", stdin);
  116.         freopen(PRL ".out", "w", stdout);
  117.     }
  118.     int tests=1;
  119.     while (tests--){
  120.         run_case();
  121.     }
  122. }
  123. // Lovely <3
  124.  
Success #stdin #stdout 0.01s 8328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3I7heA
language:
C++14 (clang 8.0)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!