Submission #987801

#	Time	Username	Problem	Language	Result	Execution time	Memory
987801		alextodoran	Examination (JOI19_examination)	C++17	100 / 100	558 ms	36384 KiB

examination

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int Q_MAX = 100000;
const int AB_MAX = (int) 1e9;

int N, Q;
int A[N_MAX + 2], B[N_MAX + 2], C[N_MAX + 2];
int X[Q_MAX + 2], Y[Q_MAX + 2], Z[Q_MAX + 2];

int values[N_MAX + Q_MAX + 2];
void compress (int V[], int W[]) {
    copy(V + 1, V + N + 1, values + 1);
    copy(W + 1, W + Q + 1, values + N + 1);
    sort(values + 1, values + N + Q + 1);
    int cnt = (unique(values + 1, values + N + Q + 1) - (values + 1));
    unordered_map <int, int> mp;
    for (int i = 1; i <= cnt; i++) {
        mp[values[i]] = i;
    }
    for (int i = 1; i <= N; i++) {
        V[i] = mp[V[i]];
    }
    for (int i = 1; i <= Q; i++) {
        W[i] = mp[W[i]];
    }
}

int ordn[N_MAX + 2], ordq[Q_MAX + 2];

vector <int> pos[N_MAX + Q_MAX + 2];
vector <int> Fen[N_MAX + Q_MAX + 2];

void pre_update (int a, int b) {
    for (int i = a; i >= 1; i -= i & -i) {
        pos[i].push_back(b);
    }
}
void build () {
    for (int i = 1; i <= N + Q; i++) {
        sort(pos[i].begin(), pos[i].end());
        pos[i].resize(unique(pos[i].begin(), pos[i].end()) - pos[i].begin());
        Fen[i].resize((int) pos[i].size() + 2);
    }
}
int get_pos (int i, int b) {
    int l = 0, r = (int) pos[i].size();
    while (l < r) {
        int mid = (l + r) / 2;
        if (b <= pos[i][mid]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l + 1;
}
void update (int a, int b) {
    for (int i = a; i >= 1; i -= i & -i) {
        for (int j = get_pos(i, b); j >= 1; j -= j & -j) {
            Fen[i][j]++;
        }
    }
}
int query (int a, int b) {
    int sum = 0;
    for (int i = a; i <= N + Q; i += i & -i) {
        for (int j = get_pos(i, b); j <= (int) pos[i].size(); j += j & -j) {
            sum += Fen[i][j];
        }
    }
    return sum;
}

int answer[Q_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];
        A[i]++; B[i]++;
        C[i] = A[i] + B[i];
    }
    for (int i = 1; i <= Q; i++) {
        cin >> X[i] >> Y[i] >> Z[i];
        X[i]++; Y[i]++; Z[i] += 2;
    }
    compress(A, X);
    compress(B, Y);
    compress(C, Z);
    iota(ordn + 1, ordn + N + 1, 1);
    iota(ordq + 1, ordq + Q + 1, 1);
    sort(ordn + 1, ordn + N + 1, [&] (const int &i, const int &j) {
        return C[i] > C[j];
    });
    sort(ordq + 1, ordq + Q + 1, [&] (const int &i, const int &j) {
        return Z[i] > Z[j];
    });
    for (int i = 1, j = 1; i <= Q; i++) {
        while (j <= N && C[ordn[j]] >= Z[ordq[i]]) {
            pre_update(A[ordn[j]], B[ordn[j]]);
            j++;
        }
    }
    build();
    for (int i = 1, j = 1; i <= Q; i++) {
        while (j <= N && C[ordn[j]] >= Z[ordq[i]]) {
            update(A[ordn[j]], B[ordn[j]]);
            j++;
        }
        answer[ordq[i]] = query(X[ordq[i]], Y[ordq[i]]);
    }
    for (int i = 1; i <= Q; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

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