답안 #640912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640912	2022-09-15T14:10:56 Z	Tenis0206	Santa Claus (RMI19_santa)	C++11	0 / 100	350 ms	13252 KB

santa

#include <bits/stdc++.h>

using namespace std;

int n;

int x[100005],v[100005];
bool h[100005];

int rez[100005],r[100005];

int nr_left = 0;

int ai[500005],lazy[500005];

void preset(int nod, int a, int b)
{
    ai[nod] = lazy[nod] = 0;
    if(a==b)
    {
        return;
    }
    int mij = (a + b) >> 1;
    preset(nod*2,a,mij);
    preset(nod*2+1,mij+1,b);
}

void propag(int nod)
{
    if(!lazy[nod])
    {
        return;
    }
    ai[nod*2] += lazy[nod];
    ai[nod*2+1] += lazy[nod];
    lazy[nod*2] += lazy[nod];
    lazy[nod*2+1] += lazy[nod];
    lazy[nod] = 0;
    return;
}

void update(int ua, int ub, int val, int nod, int a, int b)
{
    if(ua<=a && ub>=b)
    {
        ai[nod] += val;
        lazy[nod] += val;
        return;
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(ua<=mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
    ai[nod] = min(ai[nod*2],ai[nod*2+1]);
}

void add_elf(int val)
{
    update(val,n,-1,1,1,n);
}

void remove_elf(int val)
{
    update(val,n,+1,1,1,n);
}

void add_child(int val)
{
    update(val,n,+1,1,1,n);
}

void remove_child(int val)
{
    update(val,n,-1,1,1,n);
}

bool is_ok()
{
    return (ai[1] >= 0);
}

void solve_test()
{
    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])
        {
            last_elf = i;
        }
    }
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    int j = 0;
    multiset<int> s;
    int l_poz = 0;
    for(int i=1;i<=n;i++)
    {
        while(j<n && (!is_ok() || j<=last_elf || j<i))
        {
            ++j;
            if(h[j])
            {
                add_child(v[j]);
            }
            else
            {
                add_elf(v[j]);
            }
        }
        if(is_ok())
        {
            r[i] = j;
            l_poz = i;
        }
        else
        {
            break;
        }
        if(h[i]==0)
        {
            s.insert(v[i]);
        }
        else
        {
            remove_child(v[i]);
            auto dr = s.lower_bound(v[i]);
            if(dr!=s.end())
            {
                remove_elf(*dr);
                s.erase(dr);
            }
        }
    }
    r[l_poz+1] = n + 1;
    for(int i=1;i<r[1];i++)
    {
        rez[i] = -1;
    }
    for(int i=1;i<=l_poz;i++)
    {
        for(int j=r[i];j<r[i+1];j++)
        {
            rez[j] = 2 * x[j] - x[i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<rez[i]<<' ';
    }
    cout<<'\n';
    preset(1,1,n);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
//    freopen("nr.in","r",stdin);
//    freopen("nr.out","w",stdout);
    int t;
    cin>>t;
    for(int test=1; test<=t; test++)
    {
        solve_test();
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	340 KB	Output isn't correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Incorrect	7 ms	588 KB	Output isn't correct
4	Incorrect	16 ms	916 KB	Output isn't correct
5	Incorrect	42 ms	1620 KB	Output isn't correct
6	Incorrect	63 ms	2492 KB	Output isn't correct
7	Incorrect	115 ms	4600 KB	Output isn't correct
8	Incorrect	174 ms	6988 KB	Output isn't correct
9	Incorrect	258 ms	10412 KB	Output isn't correct
10	Incorrect	350 ms	13252 KB	Output isn't correct