Submission #1125614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125614		OI_Account	Examination (JOI19_examination)	C++20	100 / 100	727 ms	38572 KiB

examination

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

const int N = 100'000;
const int INF = 1'000'000'000;

int n, q, cntA, ans[N + 10];
int s[N + 10], t[N + 10], sum[N + 10];
int a[N + 10], b[N + 10], c[N + 10], cnt[4 * N + 10];
vector<pair<int, int>> all, query, seg[4 * N + 10];
vector<int> cmpA;

void readInput() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> t[i];
        sum[i] = s[i] + t[i];
        all.push_back({sum[i], i});
    }
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i];
        cmpA.push_back(a[i]);
        query.push_back({c[i], i});
    }
}

void init() {
    sort(cmpA.begin(), cmpA.end());
    sort(query.begin(), query.end());
    sort(all.begin(), all.end());
    cmpA.resize(unique(cmpA.begin(), cmpA.end()) - cmpA.begin());
    cntA = cmpA.size();
    for (int i = 1; i <= n; i++)
        s[i] = upper_bound(cmpA.begin(), cmpA.end(), s[i]) - cmpA.begin();
    for (int i = 1; i <= q; i++)
        a[i] = lower_bound(cmpA.begin(), cmpA.end(), a[i]) - cmpA.begin();
}

void addVec(int idx, int val, int id = 1, int l = 0, int r = cntA) {
    if (idx < l || r <= idx)
        return;
    seg[id].push_back({val, 0});
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    addVec(idx, val, id << 1, l, mid);
    addVec(idx, val, id << 1 | 1, mid, r);
}

void build(int id = 1, int l = 0, int r = cntA) {
    seg[id].push_back({-1, 0});
    sort(seg[id].begin(), seg[id].end());
    seg[id].resize(unique(seg[id].begin(), seg[id].end()) - seg[id].begin());
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
}

void calcSeg() {
    for (int i = 1; i <= q; i++)
        addVec(a[i], b[i]);
    build();
}

void updateFen(int t, int idx, int val) {
    for (; idx < seg[t].size(); idx += idx & -idx)
        seg[t][idx].second += val;
}

int getFen(int t, int idx) {
    int res = 0;
    for (; idx; idx -= idx & -idx)
        res += seg[t][idx].second;
    return res;
}

void update(int st, int en, int val, int id = 1, int l = 0, int r = cntA) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        int idx = lower_bound(seg[id].begin(), seg[id].end(), make_pair(val + 1, -INF)) - seg[id].begin();
        updateFen(id, idx, 1);
        cnt[id]++;
        return;
    }
    int mid = (l + r) >> 1;
    update(st, en, val, id << 1, l, mid);
    update(st, en, val, id << 1 | 1, mid, r);
}

int get(int idx, int val, int id = 1, int l = 0, int r = cntA) {
    if (idx < l || r <= idx)
        return 0;
    int pnt = lower_bound(seg[id].begin(), seg[id].end(), make_pair(val, -INF)) - seg[id].begin();
    int tmp = cnt[id] - getFen(id, pnt);
    if (l + 1 == r)
        return tmp;
    int mid = (l + r) >> 1;
    return tmp + get(idx, val, id << 1, l, mid) + get(idx, val, id << 1 | 1, mid, r);
}

void calcAns() {
    int pnt = (int) all.size();
    for (int i = (int) query.size() - 1; i >= 0; i--) {
        while (pnt && all[pnt - 1].first >= query[i].first) {
            int idx = all[pnt - 1].second;
            update(0, s[idx], t[idx]);
            pnt--;
        }
        int idx = query[i].second;
        ans[idx] = get(a[idx], b[idx]);
    }
}

void writeOutput() {
    for (int i = 1; i <= q; i++)    
        cout << ans[i] << '\n';
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    init();
    calcSeg();
    calcAns();
    writeOutput();
    return 0;
}

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