Submission #557097

#	Time	Username	Problem	Language	Result	Execution time	Memory
557097		Jomnoi	Examination (JOI19_examination)	C++17	100 / 100	221 ms	13364 KiB

examination

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 10;
const int MAX_Q = 1e5 + 10;

int S[MAX_N], T[MAX_N];
int X[MAX_Q], Y[MAX_Q], Z[MAX_Q], ans[MAX_Q];
vector <int> A, B, C;
vector <int> update, query;

class FenwickTree {
private :
    int N;
    vector <int> tree;
public :
    FenwickTree() {}
    FenwickTree(int n) : N(n), tree(N + 1, 0) {}

    void add(int x, int v) {
        for(int i = x; i <= N; i += (i & -i)) {
            tree[i] += v;
        }
    }

    int get(int x) {
        int res = 0;
        for(int i = x; i >= 1; i -= (i & -i)) {
            res += tree[i];
        }
        return res;
    }
};

int getIndex(vector <int> &a, int x) {
    return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> T[i];
        A.push_back(S[i]);
        B.push_back(T[i]);
        C.push_back(S[i] + T[i]);
    }
    for(int i = 1; i <= Q; i++) {
        cin >> X[i] >> Y[i] >> Z[i];
        A.push_back(X[i]);
        B.push_back(Y[i]);
        C.push_back(S[i] + T[i]);
    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    A.resize(unique(A.begin(), A.end()) - A.begin());
    B.resize(unique(B.begin(), B.end()) - B.begin());
    C.resize(unique(C.begin(), C.end()) - C.begin());

    int j;
    FenwickTree fwA, fwB;
    update.resize(N);
    iota(update.begin(), update.end(), 1);

    // X + Y >= Z
    fwB = FenwickTree(B.size());
    query.clear();
    for(int i = 1; i <= Q; i++) {
        if(X[i] + Y[i] >= Z[i]) {
            query.push_back(i);
        }
    }

    sort(update.begin(), update.end(), [&](const int &a, const int &b) {
        return S[a] > S[b];
    });
    sort(query.begin(), query.end(), [&](const int &a, const int &b) {
        return X[a] > X[b];
    });

    j = 0;
    for(auto i : query) {
        while(j < N and S[update[j]] >= X[i]) {
            fwB.add(getIndex(B, T[update[j]]), 1);
            j++;
        }

        ans[i] = j - fwB.get(getIndex(B, Y[i]) - 1);
    }

    // X + Y < Z
    fwA = FenwickTree(A.size());
    fwB = FenwickTree(B.size());
    query.clear();
    for(int i = 1; i <= Q; i++) {
        if(X[i] + Y[i] < Z[i]) {
            query.push_back(i);
        }
    }

    sort(update.begin(), update.end(), [&](const int &a, const int &b) {
        return S[a] + T[a] > S[b] + T[b];
    });
    sort(query.begin(), query.end(), [&](const int &a, const int &b) {
        return Z[a] > Z[b];
    });

    j = 0;
    for(auto i : query) {
        while(j < N and S[update[j]] + T[update[j]] >= Z[i]) {
            fwA.add(getIndex(A, S[update[j]]), 1);
            fwB.add(getIndex(B, T[update[j]]), 1);
            j++;
        }

        ans[i] += j - fwA.get(getIndex(A, X[i]) - 1) - fwB.get(getIndex(B, Y[i]) - 1);
    }

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

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57