Submission #847281

#	Time	Username	Problem	Language	Result	Execution time	Memory
847281		borisAngelov	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	122 ms	13904 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int inf = 1000000007;

int n, q;

struct doll
{
    int x;
    int y;
};

doll a[maxn];

struct query
{
    int minx;
    int maxy;
    int idx;
};

query queries[maxn];
int answers[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x >> a[i].y;
    }

    sort(a + 1, a + n + 1, [&](doll fr, doll sc)
    {
        if (fr.x != sc.x)
        {
            return fr.x > sc.x;
        }

        return fr.y < sc.y;
    });

    for (int i = 1; i <= q; ++i)
    {
        cin >> queries[i].minx >> queries[i].maxy;
        queries[i].idx = i;
    }

    sort(queries + 1, queries + q + 1, [&](query fr, query sc)
    {
        if (fr.minx != sc.minx)
        {
            return fr.minx > sc.minx;
        }

        return fr.maxy > sc.maxy;
    });

    vector<int> endings;

    int ptr = 1;

    for (int i = 1; i <= q; ++i)
    {
        while (ptr <= n && a[ptr].x >= queries[i].minx)
        {
            int len = upper_bound(endings.begin(), endings.end(), a[ptr].y) - endings.begin();

            if (len == endings.size())
            {
                endings.push_back(a[ptr].y);
            }
            else
            {
                endings[len] = a[ptr].y;
            }

            ++ptr;
        }

        int curr = upper_bound(endings.begin(), endings.end(), queries[i].maxy) - endings.begin();

        answers[queries[i].idx] = curr;
    }

    for (int i = 1; i <= q; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if (len == endings.size())
      |                 ~~~~^~~~~~~~~~~~~~~~~

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