제출 #1300676

#제출 시각아이디문제언어결과실행 시간메모리
1300676notisoraExamination (JOI19_examination)C++20
100 / 100
177 ms10740 KiB
#include<bits/stdc++.h>

using namespace std;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const int MAXN = 200005;

struct Element {
    int s, t, sum;
    int id;
    int type;

    bool operator<(const Element& other) const {
        if (s != other.s) return s > other.s;
        return type < other.type;
    }
};

int bit[MAXN];
int max_val;

void update(int idx, int val) {
    for (; idx <= max_val; idx += idx & -idx)
        bit[idx] += val;
}

int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx)
        res += bit[idx];
    return res;
}

vector<Element> elements;
vector<Element> temp;
int ans[MAXN];
vector<int> coords;
void cdq(int l, int r) {
    if (l >= r) return;

    int mid = (l + r) >> 1;

    cdq(l, mid);
    cdq(mid + 1, r);


    int i = l;
    int j = mid + 1;
    int k = l;
    int active_cnt = 0;

    while (i <= mid && j <= r) {
        if (elements[i].t >= elements[j].t) {
            if (elements[i].type == 0) {
                update(elements[i].sum, 1);
                active_cnt++;
            }
            temp[k++] = elements[i++];
        } else {
            if (elements[j].type == 1) {
                int count_less = query(elements[j].sum - 1);
                ans[elements[j].id] += (active_cnt - count_less);
            }
            temp[k++] = elements[j++];
        }
    }

    while (i <= mid) {
        if (elements[i].type == 0) {
            update(elements[i].sum, 1);
            active_cnt++;
        }
        temp[k++] = elements[i++];
    }

    while (j <= r) {
        if (elements[j].type == 1) {
            int count_less = query(elements[j].sum - 1);
            ans[elements[j].id] += (active_cnt - count_less);
        }
        temp[k++] = elements[j++];
    }

    for (int p = l; p <= mid; ++p) {
        if (elements[p].type == 0) {
            update(elements[p].sum, -1);
        }
    }

    for (int p = l; p <= r; ++p) {
        elements[p] = temp[p];
    }
}

int main() {
    fast_io();
//    freopen("i.INP","r",stdin);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    elements.reserve(N + Q);
    coords.reserve(N + Q);

    for (int i = 0; i < N; ++i) {
        int s, t;
        cin >> s >> t;
        elements.push_back({s, t, s + t, -1, 0});
        coords.push_back(s + t);
    }

    for (int i = 0; i < Q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        elements.push_back({x, y, z, i, 1});
        coords.push_back(z);
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    max_val = coords.size();

    for (auto& e : elements) {
        e.sum = lower_bound(coords.begin(), coords.end(), e.sum) - coords.begin() + 1;
    }

    sort(elements.begin(), elements.end());

    temp.resize(N + Q);
    memset(bit, 0, sizeof(int) * (max_val + 2));
    memset(ans, 0, sizeof(int) * Q);

    cdq(0, N + Q - 1);

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

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...