oj.uz

Submission #987801

# Submission time Handle Problem Language Result Execution time Memory
987801 2024-05-23T15:32:54 Z alextodoran Examination (JOI19_examination) C++17
100 / 100
 558 ms 36384 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 13 ms 13360 KB Output is correct
8 Correct 13 ms 13600 KB Output is correct
9 Correct 12 ms 13344 KB Output is correct
10 Correct 8 ms 13148 KB Output is correct
11 Correct 9 ms 13220 KB Output is correct
12 Correct 10 ms 13148 KB Output is correct
13 Correct 9 ms 13388 KB Output is correct
14 Correct 9 ms 13376 KB Output is correct
15 Correct 12 ms 13376 KB Output is correct
16 Correct 7 ms 13148 KB Output is correct
17 Correct 8 ms 13148 KB Output is correct
18 Correct 5 ms 12892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 31392 KB Output is correct
2 Correct 338 ms 31656 KB Output is correct
3 Correct 363 ms 31840 KB Output is correct
4 Correct 185 ms 29036 KB Output is correct
5 Correct 152 ms 24720 KB Output is correct
6 Correct 84 ms 22732 KB Output is correct
7 Correct 306 ms 30980 KB Output is correct
8 Correct 301 ms 31620 KB Output is correct
9 Correct 280 ms 31008 KB Output is correct
10 Correct 112 ms 23272 KB Output is correct
11 Correct 134 ms 28524 KB Output is correct
12 Correct 55 ms 21968 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 31392 KB Output is correct
2 Correct 338 ms 31656 KB Output is correct
3 Correct 363 ms 31840 KB Output is correct
4 Correct 185 ms 29036 KB Output is correct
5 Correct 152 ms 24720 KB Output is correct
6 Correct 84 ms 22732 KB Output is correct
7 Correct 306 ms 30980 KB Output is correct
8 Correct 301 ms 31620 KB Output is correct
9 Correct 280 ms 31008 KB Output is correct
10 Correct 112 ms 23272 KB Output is correct
11 Correct 134 ms 28524 KB Output is correct
12 Correct 55 ms 21968 KB Output is correct
13 Correct 386 ms 32748 KB Output is correct
14 Correct 360 ms 32488 KB Output is correct
15 Correct 357 ms 31888 KB Output is correct
16 Correct 194 ms 29356 KB Output is correct
17 Correct 161 ms 25008 KB Output is correct
18 Correct 82 ms 22960 KB Output is correct
19 Correct 460 ms 32588 KB Output is correct
20 Correct 412 ms 32244 KB Output is correct
21 Correct 343 ms 32064 KB Output is correct
22 Correct 109 ms 23148 KB Output is correct
23 Correct 135 ms 28392 KB Output is correct
24 Correct 55 ms 21968 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 13 ms 13360 KB Output is correct
8 Correct 13 ms 13600 KB Output is correct
9 Correct 12 ms 13344 KB Output is correct
10 Correct 8 ms 13148 KB Output is correct
11 Correct 9 ms 13220 KB Output is correct
12 Correct 10 ms 13148 KB Output is correct
13 Correct 9 ms 13388 KB Output is correct
14 Correct 9 ms 13376 KB Output is correct
15 Correct 12 ms 13376 KB Output is correct
16 Correct 7 ms 13148 KB Output is correct
17 Correct 8 ms 13148 KB Output is correct
18 Correct 5 ms 12892 KB Output is correct
19 Correct 354 ms 31392 KB Output is correct
20 Correct 338 ms 31656 KB Output is correct
21 Correct 363 ms 31840 KB Output is correct
22 Correct 185 ms 29036 KB Output is correct
23 Correct 152 ms 24720 KB Output is correct
24 Correct 84 ms 22732 KB Output is correct
25 Correct 306 ms 30980 KB Output is correct
26 Correct 301 ms 31620 KB Output is correct
27 Correct 280 ms 31008 KB Output is correct
28 Correct 112 ms 23272 KB Output is correct
29 Correct 134 ms 28524 KB Output is correct
30 Correct 55 ms 21968 KB Output is correct
31 Correct 386 ms 32748 KB Output is correct
32 Correct 360 ms 32488 KB Output is correct
33 Correct 357 ms 31888 KB Output is correct
34 Correct 194 ms 29356 KB Output is correct
35 Correct 161 ms 25008 KB Output is correct
36 Correct 82 ms 22960 KB Output is correct
37 Correct 460 ms 32588 KB Output is correct
38 Correct 412 ms 32244 KB Output is correct
39 Correct 343 ms 32064 KB Output is correct
40 Correct 109 ms 23148 KB Output is correct
41 Correct 135 ms 28392 KB Output is correct
42 Correct 55 ms 21968 KB Output is correct
43 Correct 557 ms 35916 KB Output is correct
44 Correct 558 ms 36384 KB Output is correct
45 Correct 486 ms 35696 KB Output is correct
46 Correct 323 ms 32580 KB Output is correct
47 Correct 221 ms 28144 KB Output is correct
48 Correct 88 ms 22736 KB Output is correct
49 Correct 433 ms 35456 KB Output is correct
50 Correct 531 ms 36208 KB Output is correct
51 Correct 419 ms 34620 KB Output is correct
52 Correct 192 ms 28740 KB Output is correct
53 Correct 205 ms 31100 KB Output is correct