Submission #308457

#	Time	Username	Problem	Language	Result	Execution time	Memory
308457		andreiomd	Matryoshka (JOI16_matryoshka)	C++11	51 / 100	2083 ms	14968 KiB

matryoshka

#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 2e5 + 1, QMAX = 2e5 + 1;
const int TMAX = (NMAX + QMAX - 1);

typedef pair < int, int > PII;
typedef pair < int, PII > PIII;

int N, Q;

PII A[NMAX];
PIII Queries[QMAX];

int B[(TMAX << 1)], V[(TMAX << 1)];

int ans[QMAX];

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for(int i = 1; i <= N; ++i)
    {
        cin >> A[i].first >> A[i].second;

        B[++B[0]] = A[i].first, B[++B[0]] = A[i].second;
    }

    for(int i = 1; i <= Q; ++i)
    {
        cin >> Queries[i].second.first >> Queries[i].second.second, Queries[i].first = i;

        B[++B[0]] = Queries[i].second.first, B[++B[0]] = Queries[i].second.second;
    }

    return;
}

static inline int Find (int Val)
{
    return (int)(lower_bound(V + 1, V + V[0] + 1, Val) - V);
}

static inline void Replace ()
{
    for(int i = 1; i <= N; ++i)
        A[i].first = Find(A[i].first), A[i].second = Find(A[i].second);

    for(int i = 1; i <= Q;  ++i)
        Queries[i].second.first = Find(Queries[i].second.first), Queries[i].second.second = Find(Queries[i].second.second);

    return;
}

static inline void Normalize ()
{
    sort(B + 1, B + B[0] + 1);

    V[++V[0]] = B[1];

    for(int i = 2; i <= B[0]; ++i)
        if(B[i] != B[i - 1])
            V[++V[0]] = B[i];

    Replace();

    return;
}

auto cmp_1 = [] (PII A, PII B)
{
    if(A.second < B.second)
        return 1;

    if(A.second > B.second)
        return 0;

    if(A.first > B.first)
        return 1;

    return 0;
};

auto cmp_2 = [] (PIII A, PIII B)
{
    if(A.second.second < B.second.second)
        return 1;

    return 0;
};

static inline void Sort ()
{
    sort(A + 1, A + N + 1, cmp_1);
    sort(Queries + 1, Queries + Q + 1, cmp_2);

    return;
}

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

    int List[NMAX], l = 0;
    int Stack[NMAX], k = 0;

    for(int p = 1; p <= Q; ++p)
    {
        while(Last_Valid_Position < N && A[Last_Valid_Position + 1].second <= Queries[p].second.second)
            ++Last_Valid_Position;

        l = 0;

        for(int i = 1; i <= Last_Valid_Position; ++i)
            if(A[i].first >= Queries[p].second.first)
                List[++l] = A[i].first;

        k = 0;

        for(int i = 1; i <= l; ++i)
        {
            int X = List[i];

            if(!k)
                Stack[++k] = X;
            else
            {
                int l = 1, r = k, pos = 0;

                while(l <= r)
                {
                    int m = ((l + r) >> 1);

                    if(X > Stack[m])
                        pos = m, r = m - 1;
                    else
                        l = m + 1;
                }

                if(!pos)
                    Stack[++k] = X;
                else
                    Stack[pos] = X;
            }
        }

        ans[Queries[p].first] = k;
    }

    return;
}

static inline void Write ()
{
    for(int i = 1; i <= Q; ++i)
        cout << ans[i] << '\n';

    return;
}

int main()
{
    Read();

    Normalize();

    Sort();

    Solve();

    Write();

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 49