Submission #340992

#	Time	Username	Problem	Language	Result	Execution time	Memory
340992		ijxjdjd	Examination (JOI19_examination)	C++14	2 / 100	3055 ms	8668 KiB

examination

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

using ll = long long;
const int MAXN = (int)(1e5)+5;

struct query {
    int X;
    int Y;
    int Z;
    int i;
};
vector<query> vec;
vector<int> byB;
unordered_map<int, int> cnt;
int ans[MAXN];
const int K = 3005;
int arr[MAXN];
vector<int> keep[MAXN/K + 5];
int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        arr[i] = -1;
        int A, B;
        cin >> A >> B;
        vec.push_back({A, B, -1, -1});
        byB.push_back(B);
    }
    sort(byB.begin(), byB.end());
    int c = 1;
    for (int i = 1; i < N; i++) {
        if (byB[i] != byB[i-1]) {
            cnt[byB[i-1]] = c;
        }
        c++;
    }
    cnt[byB[N-1]] = c;
    for (int i = 0; i < Q; i++) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        vec.push_back({X, Y, Z, i});
    }
    sort(vec.begin(), vec.end(), [](const query& lhs, const query& rhs) {
         if (lhs.X != rhs.X) return lhs.X > rhs.X;
        if (lhs.Y != rhs.Y) return lhs.Y > rhs.Y;
        return lhs.i < rhs.i;})
        ;
    for (query q : vec) {
        if (q.i != -1) {
            int low = 0;
            int high = N-1;
            while (low < high) {
                int mid = (low + high)/2;
                if (byB[mid] >= q.Y) {
                    high = mid;
                }
                else {
                    low = mid+1;
                }
            }
            if (byB[high] >= q.Y) {
                for (int i = N-1; i >= high;) {
                    if ((i/K)*K >= high) {
                        if (keep[i/K].size() > 0) {
                            low = 0;
                            high = keep[i/K].size()-1;
                            while (low < high) {
                                int mid = (low + high)/2;
                                if (keep[i/K][mid] >= q.Z) {
                                    high = mid;
                                }
                                else {
                                    low = mid+1;
                                }
                            }
                            if (keep[i/K][high] >= q.Z) {
                                ans[q.i] += keep[i/K].size() - high;
                            }
                        }
                        i = (i/K)*K - 1;
                    }
                    else {
                        if (arr[i] >= q.Z) {
                            ans[q.i]++;
                        }
                        i--;
                    }
                }
            }
        }
        else {
            cnt[q.Y]--;
            arr[cnt[q.Y]] = q.X + q.Y;
            keep[cnt[q.Y]/K].push_back(q.X + q.Y);
            sort(keep[cnt[q.Y]/K].begin(), keep[cnt[q.Y]/K].end());
        }
    }
    for (int i = 0; i < Q; i++) {
            cout << ans[i] << '\n';
    }
    return 0;
}

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