oj.uz

Submission #949745

# Submission time Handle Problem Language Result Execution time Memory
949745 2024-03-19T15:35:29 Z blackavar Index (COCI21_index) C++14
60 / 110
 2500 ms 55980 KB 
#include <bits/stdc++.h>
using namespace std;

const int offset = (1 << 18);

struct st{
    vector <long long> vec[offset * 2];

    void insert (long long a, long long b) {
        a += offset;
        while (a) {
            vec[a].push_back(b);
            a /= 2;
        }
    }

    void init() {
        for (int i = 0; i < offset * 2; i++) sort(vec[i].begin(), vec[i].end());
    }

    long long get(long long id, long long l, long long r, long long a, long long b, long long x) {
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return (lower_bound(vec[id].begin(), vec[id].end(), x)) - vec[id].begin();

        long long mid = (l + r) / 2;
        return get(id * 2, l, mid, a, b, x) + get(id * 2 + 1, mid + 1, r, a, b, x);
    }
}segTree;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, q;
    cin >> n >> q;
    long long a[n + 1];
    for (int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        a[i] = x;
        segTree.insert(i, x);
    }
    segTree.init();
    while (q--) {
        long long l, r;
        cin >> l >> r;
        long long lo = 1, hi = 1e9, res = -1;
        while (lo <= hi) {
            long long mid = lo + (hi - lo) / 2;
            long long cntx = r - l + 1 - segTree.get(1, 0, offset - 1, l, r, mid);
            if (cntx >= mid) {
                lo = mid + 1;
                res = mid;
            }
            else hi = mid - 1;
        }
        cout << res << "\n";
    }
    return 0;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:37:15: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   37 |     long long a[n + 1];
      |               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12888 KB Output is correct
2 Correct 14 ms 12892 KB Output is correct
3 Correct 13 ms 12892 KB Output is correct
4 Correct 11 ms 12892 KB Output is correct
5 Correct 13 ms 12888 KB Output is correct
6 Correct 14 ms 12892 KB Output is correct
7 Correct 14 ms 12888 KB Output is correct
8 Correct 11 ms 12904 KB Output is correct
9 Correct 11 ms 12892 KB Output is correct
10 Correct 11 ms 12892 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12888 KB Output is correct
2 Correct 14 ms 12892 KB Output is correct
3 Correct 13 ms 12892 KB Output is correct
4 Correct 11 ms 12892 KB Output is correct
5 Correct 13 ms 12888 KB Output is correct
6 Correct 14 ms 12892 KB Output is correct
7 Correct 14 ms 12888 KB Output is correct
8 Correct 11 ms 12904 KB Output is correct
9 Correct 11 ms 12892 KB Output is correct
10 Correct 11 ms 12892 KB Output is correct
11 Correct 735 ms 23576 KB Output is correct
12 Correct 726 ms 23524 KB Output is correct
13 Correct 730 ms 23572 KB Output is correct
14 Correct 691 ms 23636 KB Output is correct
15 Correct 732 ms 23616 KB Output is correct
16 Correct 672 ms 23472 KB Output is correct
17 Correct 697 ms 23684 KB Output is correct
18 Correct 675 ms 23616 KB Output is correct
19 Correct 695 ms 23572 KB Output is correct
20 Correct 689 ms 23740 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12888 KB Output is correct
2 Correct 14 ms 12892 KB Output is correct
3 Correct 13 ms 12892 KB Output is correct
4 Correct 11 ms 12892 KB Output is correct
5 Correct 13 ms 12888 KB Output is correct
6 Correct 14 ms 12892 KB Output is correct
7 Correct 14 ms 12888 KB Output is correct
8 Correct 11 ms 12904 KB Output is correct
9 Correct 11 ms 12892 KB Output is correct
10 Correct 11 ms 12892 KB Output is correct
11 Correct 735 ms 23576 KB Output is correct
12 Correct 726 ms 23524 KB Output is correct
13 Correct 730 ms 23572 KB Output is correct
14 Correct 691 ms 23636 KB Output is correct
15 Correct 732 ms 23616 KB Output is correct
16 Correct 672 ms 23472 KB Output is correct
17 Correct 697 ms 23684 KB Output is correct
18 Correct 675 ms 23616 KB Output is correct
19 Correct 695 ms 23572 KB Output is correct
20 Correct 689 ms 23740 KB Output is correct
21 Execution timed out 2577 ms 55980 KB Time limit exceeded
22 Halted 0 ms 0 KB -