Submission #287041

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287041	2020-08-31T09:53:56 Z	andreiomd	Santa Claus (RMI19_santa)	C++11	20 / 100	1000 ms	4216 KB

santa

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int NMAX = 96068 + 5;

int T;
int N, X[NMAX], V[NMAX];
bool H[NMAX];

int the_last_elf;

int ans[NMAX];

multiset < int > S;

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = (BSIZE - 1);
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

inline int Int ()
{
    int ans = 0;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
        {
            ans = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            ans = ans * 10 + (int)(Ch - '0');
        else
            break;
    }

    return ans;
}
};

static inline void Read ()
{
    N = InParser :: Int();

    for(int i = 1; i <= N; ++i)
        X[i] = InParser :: Int();

    the_last_elf = 0;

    for(int i = 1; i <= N; ++i)
    {
        H[i] = InParser :: Int();

        if(!H[i])
            the_last_elf = i;
    }

    for(int i = 1; i < the_last_elf; ++i)
        ans[i] = -1;

    for(int i = 1; i <= N; ++i)
        V[i] = InParser :: Int();

    return;
}

static inline bool Check (int Destination, int Middle)
{
    S.clear();

    for(int i = 1; i < Middle; ++i)
        if(H[i] == 0)
            S.insert(V[i]);
        else
        {
            auto it = S.lower_bound(V[i]);

            if(it != S.end())
                S.erase(it);
        }

    for(int i = Middle; i <= Destination; ++i)
        if(H[i] == 0)
            S.insert(V[i]);

    for(int i = Middle; i <= Destination; ++i)
        if(H[i] == 1)
        {
            auto it = S.lower_bound(V[i]);

            if(it != S.end())
                S.erase(it);
        }

    return (bool)(S.empty());
}

static inline int Go (int pos)
{
    int Left = 1, Right = pos, ans = 0;

    while(Left <= Right)
    {
        int Mid = (Left + Right) >> 1;

        if(Check(pos, Mid))
            ans = Mid, Left = Mid + 1;
        else
            Right = Mid - 1;
    }

    if(ans == 0)
        return -1;

    return ((X[pos] << 1) - X[ans]);
}

static inline void Solve ()
{
    for(int i = the_last_elf; i <= N; ++i)
        ans[i] = Go(i);

    return;
}

static inline void Write ()
{
    for(int i = 1; i <= N; ++i)
    {
        printf("%d", ans[i]);

        if(i != N)
            printf(" ");
    }

    printf("\n");

    return;
}

static inline void TestCase ()
{
    Read();

    Solve();

    Write();

    return;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    /// freopen("santaclaus.in", "r", stdin);
    /// freopen("santaclaus.out", "w", stdout);

    T = InParser :: Int();

    while(T--)
        TestCase();

    return 0;
}

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	17 ms	512 KB	Output is correct
3	Execution timed out	1091 ms	888 KB	Time limit exceeded
4	Execution timed out	1094 ms	760 KB	Time limit exceeded
5	Execution timed out	1097 ms	860 KB	Time limit exceeded
6	Execution timed out	1086 ms	1024 KB	Time limit exceeded
7	Execution timed out	1051 ms	1536 KB	Time limit exceeded
8	Execution timed out	1096 ms	2176 KB	Time limit exceeded
9	Execution timed out	1080 ms	4096 KB	Time limit exceeded
10	Execution timed out	1093 ms	4216 KB	Time limit exceeded