Submission #638722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638722	2022-09-07T07:08:47 Z	ogibogi2004	Santa Claus (RMI19_santa)	C++14	100 / 100	537 ms	14664 KB

santa

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
struct node
{
    int sum,min_sum;
};
struct segment_tree
{
    node tree[4*MAXN];
    void build(int n)
    {
        for(int i=0;i<4*n;i++)tree[i]={0,0};
    }
    void update(int l,int r,int idx,int pos,int val)
    {
        if(l>pos)return;
        if(r<pos)return;
        if(l==r)
        {
            tree[idx].sum+=val;
            tree[idx].min_sum+=val;
            return;
        }
        int mid=(l+r)/2;
        update(l,mid,idx*2,pos,val);
        update(mid+1,r,idx*2+1,pos,val);
        tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
        tree[idx].min_sum=min(tree[idx*2].min_sum,tree[idx*2].sum+tree[idx*2+1].min_sum);
    }
}st;
int n;
int x[MAXN];
int h[MAXN];
int v[MAXN];
int taken[MAXN];
int ans[MAXN];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];
    int last_elf=0;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
        if(h[i]==0)last_elf=i;
    }
    for(int i=1;i<=n;i++)cin>>v[i];
    st.build(n+2);
    for(int i=1;i<=n;i++)v[i]++;
    multiset<int>s;
    for(int i=1;i<=n;i++)
    {
        if(h[i]==0)
        {
            s.insert(v[i]);
        }
        else
        {
            auto it=s.lower_bound(v[i]);
            if(it!=s.end())
            {
                taken[i]=(*it);
                s.erase(it);
            }
            else taken[i]=-1;
        }
    }
    int l=0,r=-1;
    for(int i=0;i<n;i++)
    {
        if(h[i]==0)st.update(1,n+1,1,v[i],-1);
        else st.update(1,n+1,1,v[i],+1);
        if(i>=last_elf&&st.tree[1].min_sum>=0)
        {
            r=i;
            break;
        }
    }
    if(r==-1)
    {
        for(int i=1;i<=n;i++)cout<<"-1 ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)ans[i]=-1;
    for(;r<=n;r++)
    {
        while(l<r)
        {
            if(h[l]==1)
            {
                st.update(1,n+1,1,v[l],-1);
                if(taken[l]!=-1)
                {
                    st.update(1,n+1,1,taken[l],+1);
                }
            }
            if(st.tree[1].min_sum<0)
            {
                if(h[l]==1)
                {
                    st.update(1,n+1,1,v[l],1);
                    if(taken[l]!=-1)
                    {
                        st.update(1,n+1,1,taken[l],-1);
                    }
                }
                break;
            }
            l++;
        }
        ans[r]=2*x[r]-x[l];
        if(r!=n)
        {
            st.update(1,n+1,1,v[r+1],1);
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    cout<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	10 ms	596 KB	Output is correct
4	Correct	30 ms	956 KB	Output is correct
5	Correct	57 ms	1668 KB	Output is correct
6	Correct	97 ms	2704 KB	Output is correct
7	Correct	169 ms	4992 KB	Output is correct
8	Correct	274 ms	7428 KB	Output is correct
9	Correct	333 ms	11704 KB	Output is correct
10	Correct	537 ms	14664 KB	Output is correct