oj.uz

Submission #942567

# Submission time Handle Problem Language Result Execution time Memory
942567 2024-03-10T21:32:31 Z vjudge1 Index (COCI21_index) C++17
60 / 110
 660 ms 48584 KB 
#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

#define sz(x) (int)x.size()

const int N = 2e5+5;
int n, q;
int p[N];

vector<int> T[2*N];

void init(int i, int tl, int tr){
    if(tl == tr){
        T[i].push_back(p[tl]);
        return;
    }

    int m = (tl + tr) / 2;

    init(2*i+1, tl, m);
    init(2*i+2, m+1, tr);

    merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));

}

int query(int l, int r, int k, int i, int tl, int tr){
    if(r < tl or l > tr){
        return 0;
    }
    if(l <= tl && tr <= r){
        return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
    }
    int m = (tl + tr) / 2;
    return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}

int query(int l, int r, int k){
    return query(l, r, k, 0, 0, n-1);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    init(0, 0, n-1);

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

        int low = 1, high = r - l + 1;
        int res = 1;
        while(low <= high){
            int mid = (low + high) / 2;

            int tmp = r - l + 1 - query(l, r, mid);

            if(tmp >= mid){
                res = mid;
                low = mid+1;
            } else {
                high = mid-1;
            }

        }

        cout << res << endl;


    }

}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9820 KB Output is correct
2 Correct 9 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 6 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 631 ms 16756 KB Output is correct
12 Correct 627 ms 16600 KB Output is correct
13 Correct 626 ms 16972 KB Output is correct
14 Correct 621 ms 16736 KB Output is correct
15 Correct 625 ms 16604 KB Output is correct
16 Correct 637 ms 17376 KB Output is correct
17 Correct 636 ms 16740 KB Output is correct
18 Correct 660 ms 16588 KB Output is correct
19 Correct 621 ms 16580 KB Output is correct
20 Correct 622 ms 16900 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9820 KB Output is correct
2 Correct 9 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 6 ms 9820 KB Output is correct
9 Correct 6 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 631 ms 16756 KB Output is correct
12 Correct 627 ms 16600 KB Output is correct
13 Correct 626 ms 16972 KB Output is correct
14 Correct 621 ms 16736 KB Output is correct
15 Correct 625 ms 16604 KB Output is correct
16 Correct 637 ms 17376 KB Output is correct
17 Correct 636 ms 16740 KB Output is correct
18 Correct 660 ms 16588 KB Output is correct
19 Correct 621 ms 16580 KB Output is correct
20 Correct 622 ms 16900 KB Output is correct
21 Runtime error 63 ms 48584 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -