oj.uz

Submission #486228

# Submission time Handle Problem Language Result Execution time Memory
486228 2021-11-11T02:50:53 Z diedie Index (COCI21_index) C++17
110 / 110
 1152 ms 55820 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 5;
const int maxT = 20 * maxN;

int n, nTest;
int p[maxN];

int idx;
struct Segment {
    int left, right, val;
} st[maxT];

int root[maxN];

void update(int pos, int& node, int l, int r, int h) {
    node = ++idx;
    st[node].left = st[pos].left;
    st[node].right = st[pos].right;
    st[node].val = st[pos].val + 1;

    if (l == r) return;

    int mid = (l + r) / 2;
    if (h <= mid)
        update(st[pos].left, st[node].left, l, mid, h);
    else
        update(st[pos].right, st[node].right, mid + 1, r, h);
}

int query(int node, int l, int r, int u, int v) {
    if (l > r || l > v || r < u) return 0;
    if (u <= l && r <= v) return st[node].val;

    int mid = (l + r) / 2;
    return query(st[node].left, l, mid, u, v) + query(st[node].right, mid + 1, r, u, v);
}

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

    cin >> n >> nTest;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    vector<vector<int>> a(maxN);
    for (int i = 1; i <= n; i++)
        a[p[i]].push_back(i);

    for (int i = maxN - 1; i >= 1; i--) {
        root[i] = root[i + 1];
        for (int j : a[i])
            update(root[i], root[i], 1, n, j);
    }

    while (nTest--) {
        int l, r; cin >> l >> r;

        int ans = 0;
        int low = 1, high = maxN - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (query(root[mid], 1, n, l, r) >= mid)
                ans = mid, low = mid + 1;
            else
                high = mid - 1;
        }
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5964 KB Output is correct
2 Correct 6 ms 5964 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5964 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 8 ms 5836 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct
10 Correct 6 ms 5964 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5964 KB Output is correct
2 Correct 6 ms 5964 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5964 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 8 ms 5836 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct
10 Correct 6 ms 5964 KB Output is correct
11 Correct 216 ms 17052 KB Output is correct
12 Correct 211 ms 17008 KB Output is correct
13 Correct 211 ms 17064 KB Output is correct
14 Correct 211 ms 16964 KB Output is correct
15 Correct 218 ms 16992 KB Output is correct
16 Correct 228 ms 17080 KB Output is correct
17 Correct 218 ms 16964 KB Output is correct
18 Correct 215 ms 16964 KB Output is correct
19 Correct 234 ms 17204 KB Output is correct
20 Correct 214 ms 17000 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5964 KB Output is correct
2 Correct 6 ms 5964 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5964 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 8 ms 5836 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct
10 Correct 6 ms 5964 KB Output is correct
11 Correct 216 ms 17052 KB Output is correct
12 Correct 211 ms 17008 KB Output is correct
13 Correct 211 ms 17064 KB Output is correct
14 Correct 211 ms 16964 KB Output is correct
15 Correct 218 ms 16992 KB Output is correct
16 Correct 228 ms 17080 KB Output is correct
17 Correct 218 ms 16964 KB Output is correct
18 Correct 215 ms 16964 KB Output is correct
19 Correct 234 ms 17204 KB Output is correct
20 Correct 214 ms 17000 KB Output is correct
21 Correct 1089 ms 55708 KB Output is correct
22 Correct 1152 ms 55684 KB Output is correct
23 Correct 1088 ms 55740 KB Output is correct
24 Correct 1083 ms 55620 KB Output is correct
25 Correct 1075 ms 55616 KB Output is correct
26 Correct 1093 ms 55656 KB Output is correct
27 Correct 1079 ms 55724 KB Output is correct
28 Correct 1071 ms 55604 KB Output is correct
29 Correct 1073 ms 55624 KB Output is correct
30 Correct 1104 ms 55820 KB Output is correct