Submission #1354196

#TimeUsernameProblemLanguageResultExecution timeMemory
1354196SulAExamination (JOI19_examination)C++20
100 / 100
2670 ms7200 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

const int N = 1e5+1;
int val[N];
int n;

void update(int pos, int x) {
    val[pos] = x;
}

int query(int x, int y) {
    int ans = 0;
    for (int i = x; i < n; i++) {
        ans += y <= val[i];
    }
    return ans;
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q; cin >> n >> q;
    int S[n+1], T[n+1], posB[n+1], posC[n+1];
    pair<int,int> A[n+1], B[n+1], C[n+1];
    for (int i = 0; i < n; i++) {
        cin >> S[i] >> T[i];
        A[i] = {S[i], i};
        B[i] = {T[i], i};
        C[i] = {S[i] + T[i], i};
    }
    S[n] = 1e9+1, T[n] = 1e9+1;
    A[n] = B[n] = {1e9+1, n};
    C[n] = {2e9+2, n};
    sort(A, A + n);
    sort(B, B + n);
    sort(C, C + n);
    for (int i = 0; i <= n; i++) {
        posB[B[i].second] = i;
        posC[C[i].second] = i;
        val[i] = -1;
    }
//    for (auto [x, _] : A) cout<<_<<" "; cout << "\n";
//    for (auto [x, _] : B) cout<<_<<" "; cout << "\n";
//    for (auto [x, _] : C) cout<<_<<" "; cout << "\n";

    array<int, 4> qu[q];
    for (int i = 0; i < q; i++) {
        auto& [x, y, z, ind] = qu[i];
        ind = i;
        cin >> x >> y >> z;
        x = upper_bound(A, A + n+1, pair{x, -1}) - A;
        y = upper_bound(B, B + n+1, pair{y, -1}) - B;
        z = upper_bound(C, C + n+1, pair{z, -1}) - C;
    }
    sort(qu, qu + q, greater<>());
    int ans[q];
    int p = n-1;
    for (auto [x, y, z, ind] : qu) {
//        cout << x << " " << y << " " << z << ":\n";
        while (x <= p) {
            int i = A[p].second;
            update(posB[i], posC[i]);
            p--;
        }
//        for (int i = 0; i < n; i++) cout << val[i] << " "; cout << "\n";
        ans[ind] = query(y, z);
    }
    for (int& x : ans) cout << x << "\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...