제출 #1367530

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

using namespace std;

struct node {
    int val, left, right;
};

struct fwt {
    int n;
    vector<int> bit;

    void init(int sz) {
        n=sz;
        bit.assign(n+2, 0);
    }

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

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

    int query(int l, int r) {
        if(l > r) return 0;
        if(l == 1) return pref(r);
        return pref(r)-pref(l-1);
    }
};

vector<int> cx, cy;

int fx(int val) {
    return upper_bound(cx.begin(), cx.end(), val) - cx.begin() + 1;
}

int fy(int val) {
    return upper_bound(cy.begin(), cy.end(), val) - cy.begin() + 1;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> ans(q+2, 0);
    vector<tuple<int, int, int>> stu, stu2;
    vector<tuple<int, int, int, int>> qu1, qu2;
    for(int i=1; i<=n; i++) {
        int s, t;
        cin >> s >> t;
        stu.push_back({s, t, s+t});
        stu2.push_back({s+t, s, t});
        cx.push_back(s);
        cy.push_back(t);
    }
    for(int i=1; i<=q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        cx.push_back(x);
        cy.push_back(y);
        if(x+y >= z) qu1.push_back({x, y, z, i});
        else qu2.push_back({z, x, y, i});
    }
    sort(cx.begin(), cx.end());
    cx.erase(unique(cx.begin(), cx.end()), cx.end());
    sort(cy.begin(), cy.end());
    cy.erase(unique(cy.begin(), cy.end()), cy.end());
    sort(qu1.begin(), qu1.end());
    fwt ts, tt;
    ts.init(n+q+1);
    tt.init(n+q+1);
    sort(qu1.begin(), qu1.end());
    sort(stu.begin(), stu.end());
    int p0=n-1;
    for(int i=(int)qu1.size()-1; i>=0; i--) {
        while(p0 >= 0 && get<0>(stu[p0]) >= get<0>(qu1[i])) {
            ts.update(fy(get<1>(stu[p0])), 1);
            p0--;
        }
        ans[get<3>(qu1[i])] = ts.query(fy(get<1>(qu1[i])), n+q+1);
    }
    ts.init(n+q+1);
    int cnt = 0;
    sort(qu2.begin(), qu2.end());
    sort(stu2.begin(), stu2.end());
    p0=n-1;
    for(int i=(int)qu2.size()-1; i>=0; i--) {
        while(p0 >= 0 && get<0>(stu2[p0]) >= get<0>(qu2[i])) {
            cnt++;
            ts.update(fx(get<1>(stu2[p0])), 1);
            tt.update(fy(get<2>(stu2[p0])), 1);
            p0--;
        }
        ans[get<3>(qu2[i])] = ts.query(fx(get<1>(qu2[i])), n+q+1) + tt.query(fy(get<2>(qu2[i])), n+q+1) - cnt;
    }
    for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…