oj.uz

Submission #519279

# Submission time Handle Problem Language Result Execution time Memory
519279 2022-01-26T07:09:08 Z N1NT3NDO Index (COCI21_index) C++14
110 / 110
 2459 ms 118048 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("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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 << 1, tl, m);
    build(v * 2 + 1, m + 1, tr);

    t[v].resize(sz(t[v << 1]) + sz(t[v * 2 + 1]));
    le[v].resize(sz(t[v]));
    ri[v].resize(sz(t[v]));

    merge(all(t[v << 1]), all(t[v * 2 + 1]), t[v].begin());

    int l = 0, r = 0;
    for(int i = 0; i < sz(t[v]); i++)
    {
        int u = t[v][i];
        while(l < sz(t[v << 1]) && t[v << 1][l] < u) l++;
        while(r < sz(t[v * 2 + 1]) && t[v * 2 + 1][r] < u) r++;
        le[v][i] = l;
        ri[v][i] = 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;

    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::sync_with_stdio(0); cin.tie(0); cout.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 31 ms 56796 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56772 KB Output is correct
4 Correct 34 ms 56800 KB Output is correct
5 Correct 30 ms 56772 KB Output is correct
6 Correct 29 ms 56796 KB Output is correct
7 Correct 31 ms 56908 KB Output is correct
8 Correct 33 ms 56868 KB Output is correct
9 Correct 29 ms 56792 KB Output is correct
10 Correct 30 ms 56852 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56796 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56772 KB Output is correct
4 Correct 34 ms 56800 KB Output is correct
5 Correct 30 ms 56772 KB Output is correct
6 Correct 29 ms 56796 KB Output is correct
7 Correct 31 ms 56908 KB Output is correct
8 Correct 33 ms 56868 KB Output is correct
9 Correct 29 ms 56792 KB Output is correct
10 Correct 30 ms 56852 KB Output is correct
11 Correct 446 ms 70988 KB Output is correct
12 Correct 396 ms 71236 KB Output is correct
13 Correct 394 ms 71068 KB Output is correct
14 Correct 412 ms 71064 KB Output is correct
15 Correct 393 ms 70968 KB Output is correct
16 Correct 409 ms 71012 KB Output is correct
17 Correct 397 ms 71068 KB Output is correct
18 Correct 406 ms 71176 KB Output is correct
19 Correct 395 ms 70968 KB Output is correct
20 Correct 410 ms 71020 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 56796 KB Output is correct
2 Correct 29 ms 56776 KB Output is correct
3 Correct 30 ms 56772 KB Output is correct
4 Correct 34 ms 56800 KB Output is correct
5 Correct 30 ms 56772 KB Output is correct
6 Correct 29 ms 56796 KB Output is correct
7 Correct 31 ms 56908 KB Output is correct
8 Correct 33 ms 56868 KB Output is correct
9 Correct 29 ms 56792 KB Output is correct
10 Correct 30 ms 56852 KB Output is correct
11 Correct 446 ms 70988 KB Output is correct
12 Correct 396 ms 71236 KB Output is correct
13 Correct 394 ms 71068 KB Output is correct
14 Correct 412 ms 71064 KB Output is correct
15 Correct 393 ms 70968 KB Output is correct
16 Correct 409 ms 71012 KB Output is correct
17 Correct 397 ms 71068 KB Output is correct
18 Correct 406 ms 71176 KB Output is correct
19 Correct 395 ms 70968 KB Output is correct
20 Correct 410 ms 71020 KB Output is correct
21 Correct 2373 ms 117800 KB Output is correct
22 Correct 2448 ms 118000 KB Output is correct
23 Correct 2421 ms 117904 KB Output is correct
24 Correct 2267 ms 117952 KB Output is correct
25 Correct 2382 ms 117916 KB Output is correct
26 Correct 2459 ms 117880 KB Output is correct
27 Correct 2300 ms 118048 KB Output is correct
28 Correct 2255 ms 117960 KB Output is correct
29 Correct 2261 ms 117852 KB Output is correct
30 Correct 2342 ms 118040 KB Output is correct