Submission #1215263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215263		vanea	Examination (JOI19_examination)	C++20	100 / 100	1421 ms	7628 KiB

examination

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    int S = 2 * pow(n, .666);
    vector<vector<int>> ord(3, vector<int>(n));
    for(int i = 0; i < 3; i++) {
        iota(ord[i].begin(), ord[i].end(), 0);
    }
    for(int i = 0; i < 2; i++) {
        sort(ord[i].begin(), ord[i].end(), [&](int l, int r) {
            return a[l][i] < a[r][i];
        });
    }
    sort(ord[2].begin(), ord[2].end(), [&](int l, int r) {
        return a[l][0] + a[l][1] < a[r][0] + a[r][1];
    });
    vector<vector<int>> vals(3);
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < ord[i].size(); ++j) {
            vals[i].push_back(a[ord[i][j]][i]);
        }
    }
    for(int j = 0; j < ord[2].size(); ++j) {
        vals[2].push_back(a[ord[2][j]][0] + a[ord[2][j]][1]);
    }
    vector<array<int, 3>> qi(q), s(q);
    vector<int> qrs(q);
    iota(qrs.begin(), qrs.end(), 0);
    for(int i = 0; i < q; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> qi[i][j];
            qi[i][j] = lower_bound(vals[j].begin(), vals[j].end(), qi[i][j]) - vals[j].begin();
            s[i][j] = qi[i][j];
            if(j != 2) s[i][j] /= S;
        }
    }
    sort(qrs.begin(), qrs.end(), [&](int a, int b) {
        return s[a] < s[b];
    });
    int active = 0;
    vector<int> ans(q), cnt(n+1, 0);
    array<int, 3> curr = {n, n, n};
    for(auto idx : qrs) {
        for(int j = 0; j < 3; j++) {
            while(curr[j] > qi[idx][j]) {
                --curr[j];
                ++cnt[ord[j][curr[j]]];
                if(cnt[ord[j][curr[j]]] == 3) ++active;
            }
            while(curr[j] < qi[idx][j]) {
                --cnt[ord[j][curr[j]]];
                if(cnt[ord[j][curr[j]]] == 2) --active;
                ++curr[j];
            }
        }
        ans[idx] = active;
    }
    for(auto it : ans) {
        cout << it << '\n';
    }
    return 0;
}

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