oj.uz

Submission #519262

# Submission time Handle Problem Language Result Execution time Memory
519262 2022-01-26T06:27:38 Z N1NT3NDO Index (COCI21_index) C++14
60 / 110
 2500 ms 131608 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]))
    {
        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++;
    }

    l = 0; r = 0;

    for(int i = 0; i < sz(t[v]); i++)
    {
        int u = t[v][i];
        while(l < sz(t[v * 2]) && t[v * 2][l] < u) l++;
        while(r < sz(t[v * 2 + 1]) && t[v * 2 + 1][r] < u) r++;
        le[v].pb(l);
        ri[v].pb(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 31 ms 56884 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56792 KB Output is correct
4 Correct 29 ms 56908 KB Output is correct
5 Correct 36 ms 56892 KB Output is correct
6 Correct 31 ms 56796 KB Output is correct
7 Correct 31 ms 56796 KB Output is correct
8 Correct 30 ms 56908 KB Output is correct
9 Correct 30 ms 56908 KB Output is correct
10 Correct 30 ms 56896 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56884 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56792 KB Output is correct
4 Correct 29 ms 56908 KB Output is correct
5 Correct 36 ms 56892 KB Output is correct
6 Correct 31 ms 56796 KB Output is correct
7 Correct 31 ms 56796 KB Output is correct
8 Correct 30 ms 56908 KB Output is correct
9 Correct 30 ms 56908 KB Output is correct
10 Correct 30 ms 56896 KB Output is correct
11 Correct 446 ms 73944 KB Output is correct
12 Correct 443 ms 73940 KB Output is correct
13 Correct 529 ms 73916 KB Output is correct
14 Correct 509 ms 73960 KB Output is correct
15 Correct 482 ms 73968 KB Output is correct
16 Correct 456 ms 73964 KB Output is correct
17 Correct 483 ms 73960 KB Output is correct
18 Correct 447 ms 73984 KB Output is correct
19 Correct 470 ms 73904 KB Output is correct
20 Correct 427 ms 73968 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56884 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56792 KB Output is correct
4 Correct 29 ms 56908 KB Output is correct
5 Correct 36 ms 56892 KB Output is correct
6 Correct 31 ms 56796 KB Output is correct
7 Correct 31 ms 56796 KB Output is correct
8 Correct 30 ms 56908 KB Output is correct
9 Correct 30 ms 56908 KB Output is correct
10 Correct 30 ms 56896 KB Output is correct
11 Correct 446 ms 73944 KB Output is correct
12 Correct 443 ms 73940 KB Output is correct
13 Correct 529 ms 73916 KB Output is correct
14 Correct 509 ms 73960 KB Output is correct
15 Correct 482 ms 73968 KB Output is correct
16 Correct 456 ms 73964 KB Output is correct
17 Correct 483 ms 73960 KB Output is correct
18 Correct 447 ms 73984 KB Output is correct
19 Correct 470 ms 73904 KB Output is correct
20 Correct 427 ms 73968 KB Output is correct
21 Execution timed out 2548 ms 131608 KB Time limit exceeded
22 Halted 0 ms 0 KB -