Submission #1215152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215152		vanea	Examination (JOI19_examination)	C++20	100 / 100	2009 ms	7664 KiB

examination

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

const int mxN = 1e5+10;
const int block = pow(100000, .666);

int cnt[mxN], active = 0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
    }
    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 a, int b) {
            return v[a][i] < v[b][i];
        });
    }
    sort(ord[2].begin(), ord[2].end(), [&](int a, int b) {
        return v[a][0] + v[a][1] < v[b][1] + v[b][0];
    });
    vector<vector<int>> vals(3, vector<int>(n));
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < n; j++) {
            vals[i][j] = v[ord[i][j]][i];
        }
    }
    for(int j = 0; j < n; j++) {
        vals[2][j] = v[ord[2][j]][0] + v[ord[2][j]][1];
    }
    vector<array<int, 3>> qs(q), s(q);
    vector<int> qi(q);
    iota(qi.begin(), qi.end(), 0);
    for(int i = 0; i < q; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> qs[i][j];
            qs[i][j] = lower_bound(vals[j].begin(), vals[j].end(), qs[i][j]) - vals[j].begin();
        }
        int x = 0;
        for(int j = 0; j < 3; j++) {
            s[i][j] = qs[i][j]/block;
        }
    }
    sort(qi.begin(), qi.end(), [&](int a, int b) {
        return s[a] < s[b];
    });
    array<int, 3> curr = {n, n, n};
    vector<int> ans(q);

    for(auto id : qi) {
        for(int j = 0; j < 3; j++) {
            while(curr[j] > qs[id][j]) {
                curr[j]--;
                cnt[ord[j][curr[j]]]++;
                if(cnt[ord[j][curr[j]]] == 3) ++active;
            }
            while(curr[j] < qs[id][j]) {
                cnt[ord[j][curr[j]]]--;
                if(cnt[ord[j][curr[j]]] == 2) active--;
                curr[j]++;
            }
        }
        ans[id] = 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