oj.uz

Submission #942560

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

using namespace std;

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

#define int ll

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

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

vector<int> T[4*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 19292 KB Output is correct
2 Correct 10 ms 19292 KB Output is correct
3 Correct 9 ms 19292 KB Output is correct
4 Correct 8 ms 19444 KB Output is correct
5 Correct 10 ms 19544 KB Output is correct
6 Correct 8 ms 19292 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 9 ms 19324 KB Output is correct
9 Correct 9 ms 19292 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 10 ms 19292 KB Output is correct
3 Correct 9 ms 19292 KB Output is correct
4 Correct 8 ms 19444 KB Output is correct
5 Correct 10 ms 19544 KB Output is correct
6 Correct 8 ms 19292 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 9 ms 19324 KB Output is correct
9 Correct 9 ms 19292 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 634 ms 30148 KB Output is correct
12 Correct 632 ms 29896 KB Output is correct
13 Correct 622 ms 30004 KB Output is correct
14 Correct 649 ms 30012 KB Output is correct
15 Correct 633 ms 30152 KB Output is correct
16 Correct 631 ms 30140 KB Output is correct
17 Correct 625 ms 29900 KB Output is correct
18 Correct 626 ms 29896 KB Output is correct
19 Correct 622 ms 30244 KB Output is correct
20 Correct 627 ms 29944 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19292 KB Output is correct
2 Correct 10 ms 19292 KB Output is correct
3 Correct 9 ms 19292 KB Output is correct
4 Correct 8 ms 19444 KB Output is correct
5 Correct 10 ms 19544 KB Output is correct
6 Correct 8 ms 19292 KB Output is correct
7 Correct 8 ms 19292 KB Output is correct
8 Correct 9 ms 19324 KB Output is correct
9 Correct 9 ms 19292 KB Output is correct
10 Correct 9 ms 19292 KB Output is correct
11 Correct 634 ms 30148 KB Output is correct
12 Correct 632 ms 29896 KB Output is correct
13 Correct 622 ms 30004 KB Output is correct
14 Correct 649 ms 30012 KB Output is correct
15 Correct 633 ms 30152 KB Output is correct
16 Correct 631 ms 30140 KB Output is correct
17 Correct 625 ms 29900 KB Output is correct
18 Correct 626 ms 29896 KB Output is correct
19 Correct 622 ms 30244 KB Output is correct
20 Correct 627 ms 29944 KB Output is correct
21 Execution timed out 2563 ms 65368 KB Time limit exceeded
22 Halted 0 ms 0 KB -