oj.uz

Submission #486227

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

using ll = long long;
using pi32 = pair<int, int>;
using pi64 = pair<int64_t, int64_t>;

const int maxN = 2e5 + 5;
const int maxT = 20 * maxN;
const ll INF = 2e18 + 7;
const int MOD = 1e9 + 7;

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 5892 KB Output is correct
2 Correct 6 ms 5860 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5968 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 7 ms 5964 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 5892 KB Output is correct
2 Correct 6 ms 5860 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5968 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 7 ms 5964 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 208 ms 16968 KB Output is correct
12 Correct 210 ms 17056 KB Output is correct
13 Correct 222 ms 16996 KB Output is correct
14 Correct 217 ms 17080 KB Output is correct
15 Correct 215 ms 17040 KB Output is correct
16 Correct 220 ms 17120 KB Output is correct
17 Correct 212 ms 17056 KB Output is correct
18 Correct 214 ms 16968 KB Output is correct
19 Correct 215 ms 17080 KB Output is correct
20 Correct 215 ms 17020 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5892 KB Output is correct
2 Correct 6 ms 5860 KB Output is correct
3 Correct 5 ms 5964 KB Output is correct
4 Correct 6 ms 5968 KB Output is correct
5 Correct 6 ms 5964 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 7 ms 5964 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 208 ms 16968 KB Output is correct
12 Correct 210 ms 17056 KB Output is correct
13 Correct 222 ms 16996 KB Output is correct
14 Correct 217 ms 17080 KB Output is correct
15 Correct 215 ms 17040 KB Output is correct
16 Correct 220 ms 17120 KB Output is correct
17 Correct 212 ms 17056 KB Output is correct
18 Correct 214 ms 16968 KB Output is correct
19 Correct 215 ms 17080 KB Output is correct
20 Correct 215 ms 17020 KB Output is correct
21 Correct 1137 ms 55740 KB Output is correct
22 Correct 1084 ms 55700 KB Output is correct
23 Correct 1101 ms 55588 KB Output is correct
24 Correct 1081 ms 55616 KB Output is correct
25 Correct 1081 ms 55520 KB Output is correct
26 Correct 1084 ms 55596 KB Output is correct
27 Correct 1082 ms 55652 KB Output is correct
28 Correct 1094 ms 55720 KB Output is correct
29 Correct 1098 ms 55676 KB Output is correct
30 Correct 1076 ms 55560 KB Output is correct