oj.uz

Submission #519266

# Submission time Handle Problem Language Result Execution time Memory
519266 2022-01-26T06:40:08 Z N1NT3NDO Index (COCI21_index) C++17
110 / 110
 2498 ms 131976 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 + 1;
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::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';
    }
}

Compilation message

index.cpp:17:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
   17 | #pragma GCC optimize("avx2")
      |                            ^
index.cpp:24:33: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   24 | void build(int v, int tl, int tr)
      |                                 ^
index.cpp:50:60: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   50 | int get(int v, int tl, int tr, int l, int r, int x, int cur)
      |                                                            ^
index.cpp:66:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   66 | int main()
      |          ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56780 KB Output is correct
2 Correct 35 ms 56772 KB Output is correct
3 Correct 33 ms 56904 KB Output is correct
4 Correct 32 ms 56852 KB Output is correct
5 Correct 32 ms 56832 KB Output is correct
6 Correct 31 ms 56780 KB Output is correct
7 Correct 34 ms 56780 KB Output is correct
8 Correct 35 ms 56900 KB Output is correct
9 Correct 33 ms 56900 KB Output is correct
10 Correct 30 ms 56904 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56780 KB Output is correct
2 Correct 35 ms 56772 KB Output is correct
3 Correct 33 ms 56904 KB Output is correct
4 Correct 32 ms 56852 KB Output is correct
5 Correct 32 ms 56832 KB Output is correct
6 Correct 31 ms 56780 KB Output is correct
7 Correct 34 ms 56780 KB Output is correct
8 Correct 35 ms 56900 KB Output is correct
9 Correct 33 ms 56900 KB Output is correct
10 Correct 30 ms 56904 KB Output is correct
11 Correct 479 ms 73040 KB Output is correct
12 Correct 436 ms 73264 KB Output is correct
13 Correct 451 ms 73160 KB Output is correct
14 Correct 431 ms 73072 KB Output is correct
15 Correct 434 ms 73148 KB Output is correct
16 Correct 428 ms 73092 KB Output is correct
17 Correct 455 ms 73184 KB Output is correct
18 Correct 475 ms 73116 KB Output is correct
19 Correct 426 ms 73196 KB Output is correct
20 Correct 423 ms 73064 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56780 KB Output is correct
2 Correct 35 ms 56772 KB Output is correct
3 Correct 33 ms 56904 KB Output is correct
4 Correct 32 ms 56852 KB Output is correct
5 Correct 32 ms 56832 KB Output is correct
6 Correct 31 ms 56780 KB Output is correct
7 Correct 34 ms 56780 KB Output is correct
8 Correct 35 ms 56900 KB Output is correct
9 Correct 33 ms 56900 KB Output is correct
10 Correct 30 ms 56904 KB Output is correct
11 Correct 479 ms 73040 KB Output is correct
12 Correct 436 ms 73264 KB Output is correct
13 Correct 451 ms 73160 KB Output is correct
14 Correct 431 ms 73072 KB Output is correct
15 Correct 434 ms 73148 KB Output is correct
16 Correct 428 ms 73092 KB Output is correct
17 Correct 455 ms 73184 KB Output is correct
18 Correct 475 ms 73116 KB Output is correct
19 Correct 426 ms 73196 KB Output is correct
20 Correct 423 ms 73064 KB Output is correct
21 Correct 2488 ms 128176 KB Output is correct
22 Correct 2471 ms 128188 KB Output is correct
23 Correct 2421 ms 128236 KB Output is correct
24 Correct 2491 ms 131876 KB Output is correct
25 Correct 2385 ms 131768 KB Output is correct
26 Correct 2498 ms 131668 KB Output is correct
27 Correct 2413 ms 131976 KB Output is correct
28 Correct 2401 ms 131792 KB Output is correct
29 Correct 2382 ms 131740 KB Output is correct
30 Correct 2459 ms 131684 KB Output is correct