oj.uz

Submission #486219

# Submission time Handle Problem Language Result Execution time Memory
486219 2021-11-11T02:44:08 Z diedie Index (COCI21_index) C++17
110 / 110
 1152 ms 59500 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 >> 1;
            if (query(root[mid], 1, n, l, r) >= mid)
                ans = mid, low = mid + 1;
            else
                high = mid - 1;
        }
        cout << ans << '\n';
    }

    return 0;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:70:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5964 KB Output is correct
2 Correct 5 ms 5964 KB Output is correct
3 Correct 6 ms 5964 KB Output is correct
4 Correct 5 ms 5964 KB Output is correct
5 Correct 5 ms 5940 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 5 ms 5964 KB Output is correct
10 Correct 5 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 5 ms 5964 KB Output is correct
3 Correct 6 ms 5964 KB Output is correct
4 Correct 5 ms 5964 KB Output is correct
5 Correct 5 ms 5940 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 5 ms 5964 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 214 ms 17952 KB Output is correct
12 Correct 211 ms 17908 KB Output is correct
13 Correct 208 ms 17900 KB Output is correct
14 Correct 209 ms 17988 KB Output is correct
15 Correct 212 ms 17848 KB Output is correct
16 Correct 211 ms 17828 KB Output is correct
17 Correct 210 ms 17776 KB Output is correct
18 Correct 223 ms 17860 KB Output is correct
19 Correct 209 ms 17812 KB Output is correct
20 Correct 210 ms 17812 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 5 ms 5964 KB Output is correct
3 Correct 6 ms 5964 KB Output is correct
4 Correct 5 ms 5964 KB Output is correct
5 Correct 5 ms 5940 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 5964 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 5 ms 5964 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 214 ms 17952 KB Output is correct
12 Correct 211 ms 17908 KB Output is correct
13 Correct 208 ms 17900 KB Output is correct
14 Correct 209 ms 17988 KB Output is correct
15 Correct 212 ms 17848 KB Output is correct
16 Correct 211 ms 17828 KB Output is correct
17 Correct 210 ms 17776 KB Output is correct
18 Correct 223 ms 17860 KB Output is correct
19 Correct 209 ms 17812 KB Output is correct
20 Correct 210 ms 17812 KB Output is correct
21 Correct 1080 ms 59320 KB Output is correct
22 Correct 1101 ms 59500 KB Output is correct
23 Correct 1107 ms 59312 KB Output is correct
24 Correct 1060 ms 59260 KB Output is correct
25 Correct 1075 ms 59416 KB Output is correct
26 Correct 1082 ms 59332 KB Output is correct
27 Correct 1119 ms 59440 KB Output is correct
28 Correct 1080 ms 59232 KB Output is correct
29 Correct 1152 ms 59224 KB Output is correct
30 Correct 1100 ms 59360 KB Output is correct