oj.uz

Submission #519265

# Submission time Handle Problem Language Result Execution time Memory
519265 2022-01-26T06:34:43 Z N1NT3NDO Index (COCI21_index) C++14
60 / 110
 2500 ms 128016 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';
    }
}

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 30 ms 56856 KB Output is correct
2 Correct 29 ms 56872 KB Output is correct
3 Correct 33 ms 56796 KB Output is correct
4 Correct 29 ms 56764 KB Output is correct
5 Correct 29 ms 56880 KB Output is correct
6 Correct 29 ms 56780 KB Output is correct
7 Correct 36 ms 56780 KB Output is correct
8 Correct 29 ms 56904 KB Output is correct
9 Correct 30 ms 56888 KB Output is correct
10 Correct 29 ms 56792 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56856 KB Output is correct
2 Correct 29 ms 56872 KB Output is correct
3 Correct 33 ms 56796 KB Output is correct
4 Correct 29 ms 56764 KB Output is correct
5 Correct 29 ms 56880 KB Output is correct
6 Correct 29 ms 56780 KB Output is correct
7 Correct 36 ms 56780 KB Output is correct
8 Correct 29 ms 56904 KB Output is correct
9 Correct 30 ms 56888 KB Output is correct
10 Correct 29 ms 56792 KB Output is correct
11 Correct 437 ms 73148 KB Output is correct
12 Correct 419 ms 73228 KB Output is correct
13 Correct 424 ms 73148 KB Output is correct
14 Correct 433 ms 73148 KB Output is correct
15 Correct 420 ms 73152 KB Output is correct
16 Correct 425 ms 73136 KB Output is correct
17 Correct 441 ms 73204 KB Output is correct
18 Correct 424 ms 73112 KB Output is correct
19 Correct 429 ms 73148 KB Output is correct
20 Correct 410 ms 73044 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56856 KB Output is correct
2 Correct 29 ms 56872 KB Output is correct
3 Correct 33 ms 56796 KB Output is correct
4 Correct 29 ms 56764 KB Output is correct
5 Correct 29 ms 56880 KB Output is correct
6 Correct 29 ms 56780 KB Output is correct
7 Correct 36 ms 56780 KB Output is correct
8 Correct 29 ms 56904 KB Output is correct
9 Correct 30 ms 56888 KB Output is correct
10 Correct 29 ms 56792 KB Output is correct
11 Correct 437 ms 73148 KB Output is correct
12 Correct 419 ms 73228 KB Output is correct
13 Correct 424 ms 73148 KB Output is correct
14 Correct 433 ms 73148 KB Output is correct
15 Correct 420 ms 73152 KB Output is correct
16 Correct 425 ms 73136 KB Output is correct
17 Correct 441 ms 73204 KB Output is correct
18 Correct 424 ms 73112 KB Output is correct
19 Correct 429 ms 73148 KB Output is correct
20 Correct 410 ms 73044 KB Output is correct
21 Execution timed out 2540 ms 128016 KB Time limit exceeded
22 Halted 0 ms 0 KB -