Submission #287046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287046	2020-08-31T10:02:41 Z	andreiomd	Santa Claus (RMI19_santa)	C++11	30 / 100	1000 ms	2808 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;

int Keep = 0;

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;

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

static inline void Solve ()
{
    int last_i = 0;

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

        if(ans[i] != -1)
        {
            last_i = i;

            break;
        }
    }

    for(int i = (last_i + 1); i <= N; ++i)
    {
        while(Keep < i && Check(i, Keep + 1))
            ++Keep;

        ans[i] = ((X[i] << 1) - X[Keep]);
    }

    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

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	11 ms	384 KB	Output is correct
3	Correct	950 ms	628 KB	Output is correct
4	Execution timed out	1087 ms	760 KB	Time limit exceeded
5	Execution timed out	1082 ms	632 KB	Time limit exceeded
6	Execution timed out	1090 ms	640 KB	Time limit exceeded
7	Execution timed out	1038 ms	1024 KB	Time limit exceeded
8	Execution timed out	1092 ms	1408 KB	Time limit exceeded
9	Execution timed out	1088 ms	2560 KB	Time limit exceeded
10	Execution timed out	1035 ms	2808 KB	Time limit exceeded