Submission #62814045

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<array<int, 3>> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][2] = i;
    }
    sort(queries.begin(), queries.end(), [&](auto &one, auto &two) {
        return one[0] < two[0];
    });
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<array<int, 3>> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][2] = i;
    }
    sort(queries.begin(), queries.end(), [&](auto &one, auto &two) {
        return one[0] < two[0];
    });

    vector<int> res(q), lis;
    int completed = 0;
    for (auto [x, r, idx] : queries) {
        if (completed < x) {
            for (int i = completed; i < x; i++) {
                auto it = lower_bound(lis.begin(), lis.end(), a[i]);
                if (it == lis.end()) {
                    lis.push_back(a[i]);
                } else {
                    *it = a[i];
                }
                completed++;
            }
        }
        res[idx] = upper_bound(lis.begin(), lis.end(), r) - lis.begin();
    }

    for (int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
    return 0;
}

Submission Info

Judge Result