답안 #640765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640765 2022-09-15T07:59:45 Z Tenis0206 Santa Claus (RMI19_santa) C++11
0 / 100
442 ms 6276 KB
#include <bits/stdc++.h>

using namespace std;

int n;

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

int sel[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);
}

bool can_remove(int poz)
{
    if(h[poz]==0)
    {
        return true;
    }
    int val = v[poz];
    bool ok;
    remove_child(val);
    ok = is_ok();
    add_child(val);
    return ok;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    for(int test=1; test<=t; test++)
    {
        solve_test();
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 8 ms 468 KB Output isn't correct
4 Incorrect 21 ms 596 KB Output isn't correct
5 Incorrect 48 ms 808 KB Output isn't correct
6 Incorrect 79 ms 1192 KB Output isn't correct
7 Incorrect 148 ms 2076 KB Output isn't correct
8 Incorrect 232 ms 3280 KB Output isn't correct
9 Incorrect 305 ms 5464 KB Output isn't correct
10 Incorrect 442 ms 6276 KB Output isn't correct