oj.uz

Submission #198095

# Submission time Handle Problem Language Result Execution time Memory
198095 2020-01-24T16:47:44 Z model_code Santa Claus (RMI19_santa) C++17
20 / 100
 1000 ms 4088 KB 
/**
* 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 30 ms 376 KB Output is correct
3 Execution timed out 1036 ms 376 KB Time limit exceeded
4 Execution timed out 1050 ms 504 KB Time limit exceeded
5 Execution timed out 1020 ms 504 KB Time limit exceeded
6 Execution timed out 1033 ms 760 KB Time limit exceeded
7 Execution timed out 1050 ms 1400 KB Time limit exceeded
8 Execution timed out 1039 ms 2040 KB Time limit exceeded
9 Execution timed out 1033 ms 4088 KB Time limit exceeded
10 Execution timed out 1047 ms 4088 KB Time limit exceeded