Submission #1136931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136931		onlk97	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	55 ms	131072 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];
stack <int> seg[2100000];
void build(int id,int tl,int tr){
    if (tl==tr){
        seg[id].push(a[tl]);
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    seg[id].push(seg[2*id].top()+seg[2*id].top());
}
void gol(int id,int oriid,int dep){
    if (!dep){
        seg[id].push(seg[oriid].top());
        return;
    }
    gol(2*id,2*oriid,dep-1);
    gol(2*id+1,2*oriid+1,dep-1);
    seg[id].push(seg[2*id].top()+seg[2*id+1].top());
}
void gor(int id,int oriid,int dep){
    if (!dep){
        seg[id].top()+=seg[oriid].top();
        return;
    }
    gor(2*id,2*oriid,dep-1);
    gor(2*id+1,2*oriid+1,dep-1);
    seg[id].top()=seg[2*id].top()+seg[2*id+1].top();
}
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();
    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 <string,int> qu[q+1];
    for (int i=1; i<=q; i++){
        cin>>qu[i].x;
        qu[i].y=i;
    }
    qu[0].x="";
    for (int i=0; i<n; i++) qu[0].x+='0';
    qu[0].y=0;
    sort(qu+1,qu+q+1);
    stack <int> st;
    for (int i=0; i<=n; i++) st.push(1<<i);
    int ans[q+1];
    for (int i=1; i<=q; i++){
        int f=n;
        for (int j=0; j<n; j++){
            if (qu[i-1].x[j]!=qu[i].x[j]){
                f=j;
                break;
            }
        }
        for (int j=n-1; j>=f; j--){
            st.pop();
            if (qu[i-1].x[j]=='?') unbuild(st.top(),n-j);
        }
        for (int j=f; j<n; j++){
            if (qu[i].x[j]=='0') st.push(st.top()*2);
            else if (qu[i].x[j]=='1') st.push(st.top()*2+1);
            else {
                st.push(st.top());
                rebuild(st.top(),n-j);
            }
        }
        ans[qu[i].y]=seg[st.top()].top();
    }
    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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25