Submission #308467

#	Time	Username	Problem	Language	Result	Execution time	Memory
308467		andreiomd	Matryoshka (JOI16_matryoshka)	C++11	100 / 100	416 ms	27128 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 dp[NMAX], Best[(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 int my_max (int a, int b)
{
    return ((a > b) ? a : b);
}

class FenwickTree
{
    int a[(TMAX << 1)];

private:
    inline int UB (int X)
    {
        return (X & (-X));
    }

public:
    inline void Update (int pos, int Val)
    {
        for(int i = pos; i >= 1; i -= UB(i))
            a[i] = my_max(a[i], Val);

        return;
    }

    inline int Query (int pos)
    {
        int ans = 0;

        for(int i = pos; i <= V[0]; i += UB(i))
            ans = my_max(ans, a[i]);

        return ans;
    }
} AIB;

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

    for(int p = 1; p <= Q; ++p)
    {
        int copy = Last_Valid_Position;

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

        for(int i = (copy + 1); i <= Last_Valid_Position; ++i)
        {
            dp[i] = my_max(1, AIB.Query(A[i].first) + 1);
            AIB.Update(A[i].first, dp[i]);

            dp[i] = my_max(dp[i], Best[A[i].second] + 1);
            Best[A[i].second] = my_max(Best[A[i].second], dp[i]);
        }

        ans[Queries[p].first] = AIB.Query(Queries[p].second.first);
    }

    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: 49 / 49