Submission #1136934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136934		onlk97	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	324 ms	38148 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[1050000];
vector <int> seg[500000];
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);
}
void solve(){
    int n,q;
    cin>>n>>q;
    for (int i=1; i<=(1<<n); i++){
        char c; cin>>c;
        a[i]=(c-'0');
    }
    build(1,1,(1<<n));
    pair <long long,int> qu[q+1];
    qu[0]={0,0};
    long long pw;
    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;
    }
    sort(qu+1,qu+q+1);
    stack <int> st;
    for (int i=0; i<=n; i++) st.push(1<<i);
    int ans[q+1],f;
    for (int i=1; i<=q; i++){
        f=n;
        for (int j=0; j<2*n; j++){
            if ((qu[i-1].x&(1ll<<j))!=(qu[i].x&(1ll<<j))) f=n-j/2-1;
        }
        for (int j=n-1; j>=f; j--){
            st.pop();
            if (qu[i-1].x&(1ll<<((n-j)*2-1))) unbuild(st.top(),n-j);
        }
        for (int j=f; j<n; j++){
            if (qu[i].x&(1ll<<((n-j)*2-1))){
                st.push(st.top());
                rebuild(st.top(),n-j);
            } else if (qu[i].x&(1ll<<((n-j-1)*2))) st.push(st.top()*2+1);
            else st.push(st.top()*2);
        }
        ans[qu[i].y]=seg[st.top()].back();
    }
    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: 0 / 53
• Subtask 5: 0 / 25