oj.uz

Submission #387138

# Submission time Handle Problem Language Result Execution time Memory
387138 2021-04-08T03:40:54 Z phathnv Index (COCI21_index) C++11
110 / 110
 2457 ms 134496 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

struct Node{
    int sum;
    Node *leftChild, *rightChild;
    Node(int _x){
        sum = _x;
        leftChild = rightChild = nullptr;
    }
};

Node* Build(int l, int r){
    Node *res = new Node(0);
    if (l == r)
        return res;
    int mid = (l + r) >> 1;
    res->leftChild = Build(l, mid);
    res->rightChild = Build(mid + 1, r);
    res->sum = res->leftChild->sum + res->rightChild->sum;
    return res;
}

Node* Update(Node *cur, int l, int r, int pos){
    if (pos < l || r < pos)
        return cur;
    Node *res = new Node(1);
    if (l == r)
        return res;
    int mid = (l + r) >> 1;
    res->leftChild = Update(cur->leftChild, l, mid, pos);
    res->rightChild = Update(cur->rightChild, mid + 1, r, pos);
    res->sum = res->leftChild->sum + res->rightChild->sum;
    return res;
}

int Get(Node *cur, int l, int r, int u, int v){
    if (v < l || r < u)
        return 0;
    if (u <= l && r <= v)
        return cur->sum;
    int mid = (l + r) >> 1;
    return Get(cur->leftChild, l, mid, u, v) + Get(cur->rightChild, mid + 1, r, u, v);
}

int n, q, p[N], ind[N];
Node *ver[N], *root;

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

    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        ind[i] = i;
    }

    root = Build(1, n);
    sort(ind + 1, ind + 1 + n, [&](const int &x, const int &y){
            return p[x] > p[y];
         });
    int ptr = 1;
    for(int i = n; i >= 1; i--){
        while (ptr <= n && p[ind[ptr]] >= i)
            root = Update(root, 1, n, ind[ptr++]);
        ver[i] = root;
    }

    while (q--){
        int l, r, lo = 2, hi = n, res = 1;
        cin >> l >> r;
        while (lo <= hi){
            int mid = (lo + hi) >> 1;
            if (Get(ver[mid], 1, n, l, r) >= mid){
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cout << res << '\n';
    }

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 4 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 4 ms 748 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 355 ms 30700 KB Output is correct
12 Correct 424 ms 30700 KB Output is correct
13 Correct 355 ms 30828 KB Output is correct
14 Correct 333 ms 30700 KB Output is correct
15 Correct 338 ms 30700 KB Output is correct
16 Correct 332 ms 30848 KB Output is correct
17 Correct 345 ms 30700 KB Output is correct
18 Correct 328 ms 30828 KB Output is correct
19 Correct 366 ms 30728 KB Output is correct
20 Correct 369 ms 30724 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 4 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Correct 4 ms 748 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 4 ms 748 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 355 ms 30700 KB Output is correct
12 Correct 424 ms 30700 KB Output is correct
13 Correct 355 ms 30828 KB Output is correct
14 Correct 333 ms 30700 KB Output is correct
15 Correct 338 ms 30700 KB Output is correct
16 Correct 332 ms 30848 KB Output is correct
17 Correct 345 ms 30700 KB Output is correct
18 Correct 328 ms 30828 KB Output is correct
19 Correct 366 ms 30728 KB Output is correct
20 Correct 369 ms 30724 KB Output is correct
21 Correct 2457 ms 134264 KB Output is correct
22 Correct 2219 ms 134276 KB Output is correct
23 Correct 2170 ms 134252 KB Output is correct
24 Correct 2205 ms 134252 KB Output is correct
25 Correct 2153 ms 134496 KB Output is correct
26 Correct 2236 ms 134268 KB Output is correct
27 Correct 2208 ms 134224 KB Output is correct
28 Correct 2215 ms 134252 KB Output is correct
29 Correct 2230 ms 134252 KB Output is correct
30 Correct 2181 ms 134208 KB Output is correct