Submission #1190015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190015		onbert	Examination (JOI19_examination)	C++20	100 / 100	137 ms	12952 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
    int x, y, z, id;
    bool operator < (const thing &b) const {
        return z > b.z;
    }
};
bool cmp(pair<int,int> x, pair<int,int> y) {
    return x.first + x.second > y.first + y.second;
}
const int maxn = 1e5 + 5, maxN = 2e5 + 5;
int n;
pair<int,int> a[maxn];
int q;
thing qry[maxn];

vector<int> vals[2];
int sz[2];
int dc(int x, int i) {return lower_bound(vals[i].begin(), vals[i].end(), x) - vals[i].begin();}

int fen[maxN][2];
void update(int id, int i) {
    id++;
    while (id <= sz[i]) {
        fen[id][i]++;
        id += (id & -id);
    }
}
int sum(int id, int i) {
    id++;
    int val = 0;
    while (id >= 1) {
        val += fen[id][i];
        id -= (id & -id);
    }
    return val;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i=0;i<n;i++) {
        cin >> a[i].first >> a[i].second;
        vals[0].push_back(a[i].first);
        vals[1].push_back(a[i].second);
    }
    for (int i=0;i<q;i++) {
        int x, y, z;
        cin >> x >> y >> z;
        z = max(z, x+y);
        qry[i] = {x, y, z, i};
        vals[0].push_back(x);
        vals[1].push_back(y);
    }
    for (int i=0;i<=1;i++) {
        sort(vals[i].begin(), vals[i].end());
        vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
        sz[i] = vals[i].size();
    }
    sort(qry, qry+q);
    sort(a, a+n, cmp);
    int pt = -1, all = 0;
    int ans[q];
    for (int i=0;i<q;i++) {
        while (pt+1 < n && a[pt+1].first + a[pt+1].second >= qry[i].z) {
            pt++;
            update(dc(a[pt].first, 0), 0);
            update(dc(a[pt].second, 1), 1);
            // cout << "pt " << a[pt].first << " " << a[pt].second <<endl;
            all++;
        }
        // cout << qry[i].x << " " << dc(qry[i].x) << endl;
        // cout << "qry " << qry[i].x << endl;
        ans[qry[i].id] = all - sum(dc(qry[i].x, 0) - 1, 0) - sum(dc(qry[i].y, 1) - 1, 1);
        // cout << qry[i].id << " " << qry[i].x << " " << qry[i].y << " " << qry[i].z << endl;
        // cout << all << " " << sum(dc(qry[i].x, 0) - 1, 0) << " " << sum(dc(qry[i].y, 1) - 1, 1) << endl;
    }
    for (int i=0;i<q;i++) cout << ans[i] << "\n";
}

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