oj.uz

Submission #307808

# Submission time Handle Problem Language Result Execution time Memory
307808 2020-09-29T10:35:50 Z andreiomd None (JOI16_matryoshka) C++11
0 / 100
 1 ms 384 KB 
#include <iostream>
#include <algorithm>

using namespace std;

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

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

int N, Q;
PII A[NMAX];

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

Query List[QMAX];
int ans[QMAX];

int dp[NMAX];

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 >> List[i].second.first >> List[i].first, List[i].second.second = i;

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

    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)
        V[++V[0]] = B[i];

    return;
}

auto cmp = [] (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;
};

static inline void Sort ()
{
    sort(A + 1, A + N + 1, cmp);

    sort(List + 1, List + Q + 1);

    return;
}

static inline int my_max (int a, int b)
{
    return ((a > b) ? a : b);
}

static inline void Solve ()
{
    Sort();

    int Last_Valid_Position = 0;

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

            dp[Last_Valid_Position] = 1;

            for(int j = 1; j < Last_Valid_Position; ++j)
                if(A[j].first >= A[Last_Valid_Position].first)
                    dp[Last_Valid_Position] = my_max(dp[Last_Valid_Position], dp[j] + 1);
        }

        int cnt = 0, Max = 0;
        for(int j = 1; j <= Last_Valid_Position; ++j)
            if(A[j].first >= List[i].second.first)
                ++cnt, Max = my_max(Max, dp[j]);

        ans[List[i].second.second] = cnt - Max;
    }

    for(int i = 1; i <= Q; ++i)
        cout << ans[i] << '\n';

    return;
}

int main()
{
    Read();

    Normalize();

    Solve();

    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -