Submission #1067124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067124		Turkhuu	Examination (JOI19_examination)	C++17	100 / 100	279 ms	23464 KiB

examination

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class S> struct BIT {
    int n;vector<S> s;
    BIT(int n):n(n),s(n+1){}
    void add(int i,const S&v){for(i++;i<=n;i+=i&-i)s[i]+=v;}
    S sum(int i){S t{};for(;i;i-=i&-i)t+=s[i];return t;}
    S sum(int l,int r){return sum(r)-sum(l);}
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> S(N), T(N), A(Q), B(Q), C(Q);
    for (int i = 0; i < N; i++) cin >> S[i] >> T[i];
    for (int i = 0; i < Q; i++) cin >> A[i] >> B[i] >> C[i];
    vector<int> ans(Q), ss(S), st(T), sp(N);
    vector cnt(Q, vector<int>(8));
    for (int i = 0; i < N; i++) sp[i] = S[i] + T[i];
    sort(ss.begin(), ss.end());
    sort(st.begin(), st.end());
    sort(sp.begin(), sp.end());
    for (int i = 0; i < Q; i++) {
        if (A[i] + B[i] >= C[i]) continue;
        cnt[i][1] = lower_bound(ss.begin(), ss.end(), A[i]) - ss.begin();
        cnt[i][2] = lower_bound(st.begin(), st.end(), B[i]) - st.begin();
        cnt[i][4] = lower_bound(sp.begin(), sp.end(), C[i]) - sp.begin();
    }
    vector<int> vy, vz;
    vector<array<int, 2>> X, Y;
    for (int i = 0; i < N; i++) {
        vy.push_back(T[i]);
        vz.push_back(S[i] + T[i]);
        X.push_back({S[i], i});
        Y.push_back({T[i], i});
    }
    for (int i = 0; i < Q; i++) {
        vy.push_back(B[i]);
        vz.push_back(C[i]);
        X.push_back({A[i], ~i});
        Y.push_back({B[i], ~i});
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    sort(vy.begin(), vy.end());
    sort(vz.begin(), vz.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    vz.erase(unique(vz.begin(), vz.end()), vz.end());
    int ny = vy.size(), nz = vz.size();
    auto gety = [&](int v) {return lower_bound(vy.begin(), vy.end(), v) - vy.begin();};
    auto getz = [&](int v) {return lower_bound(vz.begin(), vz.end(), v) - vz.begin();};
    BIT<int> by(ny), bz(nz);
    for (auto [_, i] : X) {
        if (i >= 0) {
            by.add(gety(T[i]), 1);
            bz.add(getz(S[i] + T[i]), 1);
        } else {
            cnt[~i][3] += by.sum(0, gety(B[~i]));
            cnt[~i][5] += bz.sum(0, getz(C[~i]));
        }
    }
    bz = BIT<int>(nz);
    for (auto [_, i] : Y) {
        if (i >= 0) bz.add(getz(S[i] + T[i]), 1);
        else cnt[~i][6] += bz.sum(0, getz(C[~i]));
    }
    sort(X.rbegin(), X.rend());
    by = BIT<int>(ny);
    for (auto [_, i] : X) {
        if (i >= 0) by.add(gety(T[i]), 1);
        else ans[~i] = by.sum(gety(B[~i]), ny);
    }
    for (int i = 0; i < Q; i++) {
        if (A[i] + B[i] >= C[i]) continue;
        ans[i] = N;
        cnt[i][7] = cnt[i][3];
        for (int j = 1; j < 8; j++) {
            if (__builtin_parity(j)) ans[i] -= cnt[i][j];
            else ans[i] += cnt[i][j];
        }
    }
    for (auto i : ans) cout << i << "\n";
    return 6/22;
}

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