Submission #19026095

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=2e5,D=21;
int n,m,a[N],fl[1<<D],fr[1<<D],sr[D][N],sl[D][N];

//Main
int main(){
    // freopen("AGC012E.txt","r",stdin);
    // freopen("yasdf2.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    R(i,n) cin>>a[i];
    int cnt=0,log_m=2,now=1;
    for(;(now<<1)<=m;now<<=1,++log_m);
    // cout<<"log_m="<<log_m<<'\n';
    for(int l=0,r=0;l<n;++cnt,r=l=r+1)
        for(;r+1<n&&a[r+1]-a[r]<=m;++r);
    if(cnt>log_m){
        // cout<<"payixiajiuzhanqilaile,henkuaia!\n";
        R(i,n) cout<<"Impossible\n";
        return 0;
    }
    for(int t=m,d=0;t>=0;t>>=1,++d){
        for(int l=0,r=0;l<n;r=l=r+1){
            for(;r+1<n&&a[r+1]-a[r]<=t;++r);
            for(int t=l;t<=r;++t) sl[d][t]=l,sr[d][t]=r;
        }
        if(t==0) break;
    }
    R(s,1<<log_m) fr[s]=-1,fl[s]=n;
    R(s,1<<log_m){
        R(i,log_m)if(!(s>>i&1))
            fr[s|1<<i]=max(fr[s|1<<i],sr[i][fr[s]+1]),
            fl[s|1<<i]=min(fl[s|1<<i],sl[i][fl[s]-1]);
    }
    // R(s,1<<log_m) cout<<"s="<<s<<" fr="
    //     <<fr[s]<<" fl="<<fl[s]<<'\n';
    for(int l=0,r=0;l<n;r=l=r+1){
        for(;r+1<n&&a[r+1]-a[r]<=m;++r);
        bool poss=false;
        R(s,1<<log_m)if(!(s&1)&&fr[s]>=l-1
            &&fl[((1<<log_m)-2)^s]<=r+1){poss=true; break;}
        R(t,r-l+1) cout<<string(poss?"P":"Imp")+"ossible\n";
    }
    return 0;
}

Submission Info

Judge Result