Submission #1193282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193282		GoBananas69	Examination (JOI19_examination)	C++20	2 / 100	552 ms	1114112 KiB

examination

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Query {
    int s, t, sum;
    int type; // 0: insertion, 1: query
    int idx; // original index for queries
};

class BIT2D {
private:
    vector<vector<int>> tree;
    int sizeT, sizeSum;

public:
    BIT2D(int t_size, int sum_size) : sizeT(t_size), sizeSum(sum_size) {
        tree.resize(t_size + 1, vector<int>(sum_size + 1, 0));
    }

    void update(int t, int sum, int delta) {
        for (int i = t; i <= sizeT; i += i & -i) {
            for (int j = sum; j <= sizeSum; j += j & -j) {
                tree[i][j] += delta;
            }
        }
    }

    int query(int t, int sum) {
        int res = 0;
        for (int i = t; i > 0; i -= i & -i) {
            for (int j = sum; j > 0; j -= j & -j) {
                res += tree[i][j];
            }
        }
        return res;
    }
};

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

    int n, k;
    cin >> n >> k;

    vector<Query> events;

    // Read insertions
    for (int i = 0; i < n; ++i) {
        int s, t;
        cin >> s >> t;
        int sum = s + t;
        events.push_back({s, t, sum, 0, -1});
    }

    // Read queries
    for (int i = 0; i < k; ++i) {
        int s, t, sum;
        cin >> s >> t >> sum;
        events.push_back({s, t, sum, 1, i});
    }

    // Sort events by s descending, t descending, sum descending, insertions first
    sort(events.begin(), events.end(), [](const Query& a, const Query& b) {
        if (a.s != b.s) return a.s > b.s;
        if (a.t != b.t) return a.t > b.t;
        if (a.sum != b.sum) return a.sum > b.sum;
        return a.type < b.type; // insertions come before queries if all else equal
    });

    // Collect all t and sum values for compression
    vector<int> t_values, sum_values;
    for (const auto& event : events) {
        t_values.push_back(event.t);
        sum_values.push_back(event.sum);
    }

    // Compress t
    sort(t_values.begin(), t_values.end());
    t_values.erase(unique(t_values.begin(), t_values.end()), t_values.end());
    int t_size = t_values.size();

    // Compress sum
    sort(sum_values.begin(), sum_values.end());
    sum_values.erase(unique(sum_values.begin(), sum_values.end()), sum_values.end());
    int sum_size = sum_values.size();

    // Function to get compressed t rank
    auto get_t_rank = [&](int t) {
        auto it = lower_bound(t_values.begin(), t_values.end(), t);
        return (it - t_values.begin()) + 1; // ranks start from 1
    };

    // Function to get compressed sum rank
    auto get_sum_rank = [&](int sum) {
        auto it = lower_bound(sum_values.begin(), sum_values.end(), sum);
        return (it - sum_values.begin()) + 1;
    };

    BIT2D bit(t_size, sum_size);
    vector<int> res(k, 0);

    for (const auto& event : events) {
        if (event.type == 0) { // Insertion
            int t_rank = get_t_rank(event.t);
            int sum_rank = get_sum_rank(event.sum);
            bit.update(t_rank, sum_rank, 1);
        } else { // Query
            int t_rank = get_t_rank(event.t);
            int sum_rank = get_sum_rank(event.sum);

            int M = t_size;
            int N = sum_size;

            int part1 = bit.query(M, N);
            int part2 = (t_rank > 1) ? bit.query(t_rank - 1, N) : 0;
            int part3 = (sum_rank > 1) ? bit.query(M, sum_rank - 1) : 0;
            int part4 = (t_rank > 1 && sum_rank > 1) ? bit.query(t_rank - 1, sum_rank - 1) : 0;

            int cnt = part1 - part2 - part3 + part4;
            res[event.idx] = cnt;
        }
    }

    for (int i = 0; i < k; ++i) {
        cout << res[i] << '\n';
    }

    return 0;
}

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