oj.uz

Submission #486223

# Submission time Handle Problem Language Result Execution time Memory
486223 2021-11-11T02:46:32 Z diedie Index (COCI21_index) C++17
110 / 110
 1202 ms 55668 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 6 ms 6080 KB Output is correct
3 Correct 6 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 6 ms 5964 KB Output is correct
7 Correct 6 ms 5964 KB Output is correct
8 Correct 6 ms 5968 KB Output is correct
9 Correct 6 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 6 ms 6080 KB Output is correct
3 Correct 6 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 6 ms 5964 KB Output is correct
7 Correct 6 ms 5964 KB Output is correct
8 Correct 6 ms 5968 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 231 ms 17092 KB Output is correct
12 Correct 225 ms 17168 KB Output is correct
13 Correct 225 ms 17040 KB Output is correct
14 Correct 213 ms 17088 KB Output is correct
15 Correct 224 ms 17316 KB Output is correct
16 Correct 216 ms 17068 KB Output is correct
17 Correct 213 ms 16964 KB Output is correct
18 Correct 225 ms 17332 KB Output is correct
19 Correct 219 ms 17080 KB Output is correct
20 Correct 216 ms 16976 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 6080 KB Output is correct
3 Correct 6 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 6 ms 5964 KB Output is correct
7 Correct 6 ms 5964 KB Output is correct
8 Correct 6 ms 5968 KB Output is correct
9 Correct 6 ms 5964 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 231 ms 17092 KB Output is correct
12 Correct 225 ms 17168 KB Output is correct
13 Correct 225 ms 17040 KB Output is correct
14 Correct 213 ms 17088 KB Output is correct
15 Correct 224 ms 17316 KB Output is correct
16 Correct 216 ms 17068 KB Output is correct
17 Correct 213 ms 16964 KB Output is correct
18 Correct 225 ms 17332 KB Output is correct
19 Correct 219 ms 17080 KB Output is correct
20 Correct 216 ms 16976 KB Output is correct
21 Correct 1104 ms 55532 KB Output is correct
22 Correct 1142 ms 55664 KB Output is correct
23 Correct 1115 ms 55608 KB Output is correct
24 Correct 1113 ms 55640 KB Output is correct
25 Correct 1131 ms 55668 KB Output is correct
26 Correct 1121 ms 55576 KB Output is correct
27 Correct 1132 ms 55524 KB Output is correct
28 Correct 1156 ms 55536 KB Output is correct
29 Correct 1126 ms 55596 KB Output is correct
30 Correct 1202 ms 55532 KB Output is correct