oj.uz

Submission #942551

# Submission time Handle Problem Language Result Execution time Memory
942551 2024-03-10T20:53:37 Z vjudge1 Index (COCI21_index) C++17
20 / 110
 2500 ms 2400 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()

signed main(){
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    for(auto &i : p){
        cin >> i;
    }

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

        vector<int> tmp;
        for(int i=l; i<=r; ++i){
            tmp.push_back(p[i]);
        }
        sort(tmp.rbegin(), tmp.rend());
        
        assert(sz(tmp) == r-l+1);

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

            if(tmp[mid-1] >= 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 37 ms 344 KB Output is correct
2 Correct 37 ms 348 KB Output is correct
3 Correct 38 ms 348 KB Output is correct
4 Correct 38 ms 348 KB Output is correct
5 Correct 38 ms 348 KB Output is correct
6 Correct 37 ms 348 KB Output is correct
7 Correct 40 ms 600 KB Output is correct
8 Correct 38 ms 344 KB Output is correct
9 Correct 38 ms 348 KB Output is correct
10 Correct 38 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB Output is correct
2 Correct 37 ms 348 KB Output is correct
3 Correct 38 ms 348 KB Output is correct
4 Correct 38 ms 348 KB Output is correct
5 Correct 38 ms 348 KB Output is correct
6 Correct 37 ms 348 KB Output is correct
7 Correct 40 ms 600 KB Output is correct
8 Correct 38 ms 344 KB Output is correct
9 Correct 38 ms 348 KB Output is correct
10 Correct 38 ms 348 KB Output is correct
11 Execution timed out 2547 ms 2400 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 344 KB Output is correct
2 Correct 37 ms 348 KB Output is correct
3 Correct 38 ms 348 KB Output is correct
4 Correct 38 ms 348 KB Output is correct
5 Correct 38 ms 348 KB Output is correct
6 Correct 37 ms 348 KB Output is correct
7 Correct 40 ms 600 KB Output is correct
8 Correct 38 ms 344 KB Output is correct
9 Correct 38 ms 348 KB Output is correct
10 Correct 38 ms 348 KB Output is correct
11 Execution timed out 2547 ms 2400 KB Time limit exceeded
12 Halted 0 ms 0 KB -