oj.uz

Submission #519263

# Submission time Handle Problem Language Result Execution time Memory
519263 2022-01-26T06:30:45 Z N1NT3NDO Index (COCI21_index) C++14
60 / 110
 2500 ms 128112 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("avx2")

const int N = (int)2e5 + 5;
vector< int > t[4 * N], le[4 * N], ri[4 * N];
int a[N];
int n, q;

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v].pb(a[tl]);
        return;
    }

    int m = (tl + tr) >> 1;

    build(v * 2, tl, m);
    build(v * 2 + 1, m + 1, tr);

    int l = 0, r = 0;
    while(l < sz(t[v * 2]) || r < sz(t[v * 2 + 1]))
    {
        le[v].pb(l);
        ri[v].pb(r);
        if (l == sz(t[v * 2])) t[v].pb(t[v * 2 + 1][r]), r++;
        else if (r == sz(t[v * 2 + 1])) t[v].pb(t[v * 2][l]), l++;
        else if (t[v * 2][l] < t[v * 2 + 1][r]) t[v].pb(t[v * 2][l]), l++;
        else t[v].pb(t[v * 2 + 1][r]), r++;
    }

}

int get(int v, int tl, int tr, int l, int r, int x, int cur)
{
    if (tl > tr || tr < l || tl > r || cur >= sz(t[v])) return 0;

    if (v == 1)
      cur = lower_bound(all(t[v]), x) - t[v].begin();

    if (tl >= l && tr <= r)
      return sz(t[v]) - cur;

    int m = (tl + tr) >> 1;

    return get(v * 2, tl, m, l, r, x, le[v][cur]) + get(v * 2 + 1, m + 1, tr, l, r, x, ri[v][cur]);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        int lo = 1, hi = r - l + 1;
        while(lo < hi)
        {
            int mid = (lo + hi + 1) >> 1;

            if (get(1, 1, n, l, r, mid, 0) >= mid) lo = mid;
            else hi = mid - 1;
        }

        cout << lo << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56872 KB Output is correct
2 Correct 28 ms 56904 KB Output is correct
3 Correct 30 ms 56864 KB Output is correct
4 Correct 30 ms 56792 KB Output is correct
5 Correct 30 ms 56832 KB Output is correct
6 Correct 32 ms 56776 KB Output is correct
7 Correct 33 ms 56780 KB Output is correct
8 Correct 28 ms 56976 KB Output is correct
9 Correct 30 ms 56884 KB Output is correct
10 Correct 30 ms 56824 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56872 KB Output is correct
2 Correct 28 ms 56904 KB Output is correct
3 Correct 30 ms 56864 KB Output is correct
4 Correct 30 ms 56792 KB Output is correct
5 Correct 30 ms 56832 KB Output is correct
6 Correct 32 ms 56776 KB Output is correct
7 Correct 33 ms 56780 KB Output is correct
8 Correct 28 ms 56976 KB Output is correct
9 Correct 30 ms 56884 KB Output is correct
10 Correct 30 ms 56824 KB Output is correct
11 Correct 502 ms 73160 KB Output is correct
12 Correct 440 ms 73100 KB Output is correct
13 Correct 424 ms 73144 KB Output is correct
14 Correct 415 ms 73108 KB Output is correct
15 Correct 426 ms 73184 KB Output is correct
16 Correct 468 ms 73116 KB Output is correct
17 Correct 448 ms 73156 KB Output is correct
18 Correct 451 ms 73204 KB Output is correct
19 Correct 420 ms 73080 KB Output is correct
20 Correct 424 ms 73052 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56872 KB Output is correct
2 Correct 28 ms 56904 KB Output is correct
3 Correct 30 ms 56864 KB Output is correct
4 Correct 30 ms 56792 KB Output is correct
5 Correct 30 ms 56832 KB Output is correct
6 Correct 32 ms 56776 KB Output is correct
7 Correct 33 ms 56780 KB Output is correct
8 Correct 28 ms 56976 KB Output is correct
9 Correct 30 ms 56884 KB Output is correct
10 Correct 30 ms 56824 KB Output is correct
11 Correct 502 ms 73160 KB Output is correct
12 Correct 440 ms 73100 KB Output is correct
13 Correct 424 ms 73144 KB Output is correct
14 Correct 415 ms 73108 KB Output is correct
15 Correct 426 ms 73184 KB Output is correct
16 Correct 468 ms 73116 KB Output is correct
17 Correct 448 ms 73156 KB Output is correct
18 Correct 451 ms 73204 KB Output is correct
19 Correct 420 ms 73080 KB Output is correct
20 Correct 424 ms 73052 KB Output is correct
21 Execution timed out 2531 ms 128112 KB Time limit exceeded
22 Halted 0 ms 0 KB -