Submission #198095

#	Time	Username	Problem	Language	Result	Execution time	Memory
198095		model_code	Santa Claus (RMI19_santa)	C++17	20 / 100	1050 ms	4088 KiB

santa

/**
* user:  melnyk-1f2
* fname: Sofiia
* lname: Melnyk
* task:  santa
* score: 20.0
* date:  2019-10-11 06:54:57.882096
*/
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 2e5 + 11;

int x[N],h[N],v[N];
set<pair<int,int> > stt;

bool good(int mn, int i)
{
    stt.clear();
    for (int j=1; j<mn; j++)
    {
        if (h[j]==0) stt.insert(mp(v[j],j)); else
        {
            auto it=stt.lower_bound(mp(v[j],0));
            if (it==stt.end()) continue;
            stt.erase(it);
        }
    }
    for (int j=mn; j<=i; j++)
        if (h[j]==0) stt.insert(mp(v[j],j));
    for (int j=mn; j<=i; j++)
        if (h[j]==1)
    {
        auto it=stt.lower_bound(mp(v[j],0));
        if (it==stt.end()) continue;
        stt.erase(it);
    }
    if ((int)stt.size()==0) return true;
    return false;
}

void up()
{
    int n;
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>x[i];
    int t=0;
    for (int i=1; i<=n; i++)
        {
            cin>>h[i];
            if (h[i]==0) t++;
        }
    for (int i=1; i<=n; i++)
        cin>>v[i];
    vector<int> vs;
    set<pair<int,int> > st,stt;
    for (int i=1; i<=n; i++)
    {
        if (h[i]==0) st.insert(mp(v[i],i));
        if ((int)st.size()==t)
        {
            int ans=-1;
            int l=1,r=i;
            while (r-l>1)
            {
                int mid=(l+r)/2;
                if (good(mid,i)) l=mid; else r=mid;
            }
            if (good(r,i)) ans=x[i]+x[i]-x[r]; else
            if (good(l,i)) ans=x[i]+x[i]-x[l]; else ans=-1;
            cout<<ans<<" ";
        } else cout<<-1<<" ";
    }
    cout<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while (t--) up();
}
/**
4
8
10 11 12 13 14 16 25 35
1 0 0 0 1 1 1 1
2 2 3 3 5 1 1 1
16
10 11 12 13 14 15 16 17 18 19 20 23 24 31 33 37
1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1
2 1 7 3 1 10 10 6 5 5 1 6 1 10 8 2
9
1 2 3 4 15 16 17 18 19
0 0 1 1 1 0 0 1 1
5 7 4 1 2 3 1 6 2
9
1 2 3 4 15 16 17 18 19
0 0 1 1 1 0 0 1 1
5 7 4 1 2 3 1 6 1
**/

• Subtask 1: 20 / 100