Submission #1136938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136938		onlk97	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	1042 ms	65800 KiB

snake_escaping

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int a[(1<<17)+1];
vector <int> seg[(1<<18)+1];
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id].pb(a[tl]);
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    seg[id].pb(seg[2*id][0]+seg[2*id][1]);
}
void gol(int id,int oriid,int dep){
    if (!dep){
        seg[id].pb(seg[oriid].back());
        return;
    }
    gol(2*id,2*oriid,dep-1);
    gol(2*id+1,2*oriid+1,dep-1);
    seg[id].pb(seg[2*id].back()+seg[2*id+1].back());
}
void gor(int id,int oriid,int dep){
    if (!dep){
        seg[id].back()+=seg[oriid].back();
        return;
    }
    gor(2*id,2*oriid,dep-1);
    gor(2*id+1,2*oriid+1,dep-1);
    seg[id].back()=seg[2*id].back()+seg[2*id+1].back();
}
void rebuild(int id,int dep){
    gol(id,2*id,dep-1);
    gor(id,2*id+1,dep-1);
}
void unbuild(int id,int dep){
    seg[id].pop_back();
    if (dep<=1) return;
    unbuild(2*id,dep-1);
    unbuild(2*id+1,dep-1);
}
int N;
int ans[1000010];
pair <long long,int> want[1000010];
int idxwant;
void answer(){
    build(1,1,(1<<N));
    long long pw=1;
    sort(want+1,want+idxwant+1);
    stack <int> st;
    for (int i=0; i<=N; i++) st.push(1<<i);
    int f;
    for (int i=1; i<=idxwant; i++){
        f=N;
        for (int j=0; j<2*N; j++){
            if ((want[i-1].x&(1ll<<j))!=(want[i].x&(1ll<<j))) f=N-j/2-1;
        }
        for (int j=N-1; j>=f; j--){
            st.pop();
            if (want[i-1].x&(1ll<<((N-j)*2-1))) unbuild(st.top(),N-j);
        }
        for (int j=f; j<N; j++){
            if (want[i].x&(1ll<<((N-j)*2-1))){
                st.push(st.top());
                rebuild(st.top(),N-j);
            } else if (want[i].x&(1ll<<((N-j-1)*2))) st.push(st.top()*2+1);
            else st.push(st.top()*2);
        }
        ans[want[i].y]+=seg[st.top()].back();
    }
    for (int i=1; i<(1<<(N-1)); i++) seg[i].clear();
}
pair <long long,int> qu[1000010];
void solve(){
    int n,q;
    cin>>n>>q;
    int arr[(1<<n)+1];
    for (int i=1; i<=(1<<n); i++){
        char c; cin>>c;
        arr[i]=(c-'0');
    }
    long long pw=1;
    for (int i=1; i<=q; i++){
        string str; cin>>str;
        qu[i].x=0;
        pw=1;
        for (int j=n-1; j>=0; j--){
            if (str[j]=='?') qu[i].x+=pw*2;
            else if (str[j]=='1') qu[i].x+=pw;
            pw*=4;
        }
        qu[i].y=i;
    }
    if (n<=17){
        N=n;
        for (int i=1; i<=(1<<n); i++) a[i]=arr[i];
        for (int i=1; i<=q; i++) want[i]=qu[i];
        idxwant=q;
        answer();
    } else {
        N=17;
        for (int mask=0; mask<8; mask++){
            for (int i=1; i<=(1<<N); i++) a[i]=arr[8*(i-1)+mask+1];
            idxwant=0;
            for (int i=1; i<=q; i++){
                int b0=(mask&1);
                if (b0&&qu[i].x%4==0) continue;
                if (!b0&&qu[i].x%4==1) continue;
                int b1=(mask>>1)&1;
                if (b1&&(qu[i].x>>2)%4==0) continue;
                if (!b1&&(qu[i].x>>2)%4==1) continue;
                int b2=(mask>>2)&1;
                if (b2&&(qu[i].x>>4)%4==0) continue;
                if (!b2&&(qu[i].x>>4)%4==1) continue;
                want[++idxwant]={(qu[i].x>>6),qu[i].y};
            }
            answer();
        }
    }
    for (int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25