Submission #1309735

#TimeUsernameProblemLanguageResultExecution timeMemory
1309735kawhietExamination (JOI19_examination)C++20
2 / 100
3093 ms2884 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> s(n), t(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> t[i];
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    ranges::sort(ord, [&](int i, int j) {
        return s[i] + t[i] < s[j] + t[j];
    });
    vector<int> a(n), b(n), k(n);
    for (int i = 0; i < n; i++) {
        a[i] = s[ord[i]];
        b[i] = t[ord[i]];
        k[i] = a[i] + b[i];
    }
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        z = max(z, x + y);
        int pos = ranges::lower_bound(k, z) - k.begin();
        if (pos == n) {
            cout << 0 << '\n';
            continue;
        }
        int ans = n - pos;
        for (int i = pos; i < n; i++) {
            if (a[i] < x) {
                ans--;
            }
            if (b[i] < y) {
                ans--;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

// a[i] >= x
// b[i] >= y
// a[i] + b[i] >= z >= x + y
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...