oj.uz

Submission #519264

# Submission time Handle Problem Language Result Execution time Memory
519264 2022-01-26T06:34:05 Z N1NT3NDO Index (COCI21_index) C++14
60 / 110
 2500 ms 131980 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 (tl >= l && tr <= r)
      return sz(t[v]) - cur;

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

    int lft = 0, rht = 0;
    if (le[v][cur] < sz(t[v * 2])) lft = get(v * 2, tl, m, l, r, x, le[v][cur]);
    if (ri[v][cur] < sz(t[v * 2 + 1])) rht = get(v * 2 + 1, m + 1, tr, l, r, x, ri[v][cur]);

    return lft + rht;
}

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, lower_bound(all(t[1]), mid) - t[1].begin()) >= mid) lo = mid;
            else hi = mid - 1;
        }

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56780 KB Output is correct
2 Correct 31 ms 56908 KB Output is correct
3 Correct 31 ms 56880 KB Output is correct
4 Correct 29 ms 56900 KB Output is correct
5 Correct 35 ms 56768 KB Output is correct
6 Correct 30 ms 56772 KB Output is correct
7 Correct 32 ms 56808 KB Output is correct
8 Correct 29 ms 56844 KB Output is correct
9 Correct 30 ms 56892 KB Output is correct
10 Correct 29 ms 56780 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56780 KB Output is correct
2 Correct 31 ms 56908 KB Output is correct
3 Correct 31 ms 56880 KB Output is correct
4 Correct 29 ms 56900 KB Output is correct
5 Correct 35 ms 56768 KB Output is correct
6 Correct 30 ms 56772 KB Output is correct
7 Correct 32 ms 56808 KB Output is correct
8 Correct 29 ms 56844 KB Output is correct
9 Correct 30 ms 56892 KB Output is correct
10 Correct 29 ms 56780 KB Output is correct
11 Correct 502 ms 73048 KB Output is correct
12 Correct 470 ms 73060 KB Output is correct
13 Correct 428 ms 73192 KB Output is correct
14 Correct 412 ms 73148 KB Output is correct
15 Correct 437 ms 73044 KB Output is correct
16 Correct 425 ms 73092 KB Output is correct
17 Correct 414 ms 73148 KB Output is correct
18 Correct 426 ms 73064 KB Output is correct
19 Correct 424 ms 73044 KB Output is correct
20 Correct 469 ms 73104 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56780 KB Output is correct
2 Correct 31 ms 56908 KB Output is correct
3 Correct 31 ms 56880 KB Output is correct
4 Correct 29 ms 56900 KB Output is correct
5 Correct 35 ms 56768 KB Output is correct
6 Correct 30 ms 56772 KB Output is correct
7 Correct 32 ms 56808 KB Output is correct
8 Correct 29 ms 56844 KB Output is correct
9 Correct 30 ms 56892 KB Output is correct
10 Correct 29 ms 56780 KB Output is correct
11 Correct 502 ms 73048 KB Output is correct
12 Correct 470 ms 73060 KB Output is correct
13 Correct 428 ms 73192 KB Output is correct
14 Correct 412 ms 73148 KB Output is correct
15 Correct 437 ms 73044 KB Output is correct
16 Correct 425 ms 73092 KB Output is correct
17 Correct 414 ms 73148 KB Output is correct
18 Correct 426 ms 73064 KB Output is correct
19 Correct 424 ms 73044 KB Output is correct
20 Correct 469 ms 73104 KB Output is correct
21 Correct 2433 ms 128068 KB Output is correct
22 Correct 2381 ms 131980 KB Output is correct
23 Execution timed out 2503 ms 131820 KB Time limit exceeded
24 Halted 0 ms 0 KB -