oj.uz

Submission #537830

# Submission time Handle Problem Language Result Execution time Memory
537830 2022-03-15T16:20:25 Z N1NT3NDO Index (COCI21_index) C++14
110 / 110
 936 ms 10032 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 5;
const int M = 450;
int n, a[N], f[N], m, ans[N];

struct que{
    int l, r, idx;
};

bool cmp(const que &a, const que &b)
{
    if (a.l / M != b.l / M)
      return a.l < b.l;
    else return a.r < b.r;
}

void upd(int x, int val)
{
    for(int i = x; i < N; i += i & -i) f[i] += val;
}

int get(int x)
{
    int res = 0;
    for(int i = x; i > 0; i -= i & -i) res += f[i];
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector< que > queries;
    for(int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        queries.pb({l, r, i});
    }

    sort(all(queries), cmp);

    int cur_l = 1, cur_r = 0;

    for(auto [l, r, nom] : queries)
    {
        while(cur_l > l)
        {
            cur_l--;
            upd(a[cur_l], 1);
        }

        while(cur_r < r)
        {
            cur_r++;
            upd(a[cur_r], 1);
        }

        while(cur_l < l)
        {
            upd(a[cur_l], -1);
            cur_l++;
        }

        while(cur_r > r)
        {
            upd(a[cur_r], -1);
            cur_r--;
        }

        int L = 1, R = r - l + 1;
        while(L < R)
        {
            int m = (L + R + 1) >> 1;
            if (get(N - 1) - get(m - 1) >= m) L = m;
            else R = m - 1;
        }

        ans[nom] = L;
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [l, r, nom] : queries)
      |              ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 336 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 200 ms 2740 KB Output is correct
12 Correct 215 ms 2744 KB Output is correct
13 Correct 214 ms 2724 KB Output is correct
14 Correct 197 ms 2728 KB Output is correct
15 Correct 215 ms 2724 KB Output is correct
16 Correct 203 ms 2728 KB Output is correct
17 Correct 199 ms 2732 KB Output is correct
18 Correct 198 ms 2728 KB Output is correct
19 Correct 238 ms 2720 KB Output is correct
20 Correct 198 ms 2728 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 200 ms 2740 KB Output is correct
12 Correct 215 ms 2744 KB Output is correct
13 Correct 214 ms 2724 KB Output is correct
14 Correct 197 ms 2728 KB Output is correct
15 Correct 215 ms 2724 KB Output is correct
16 Correct 203 ms 2728 KB Output is correct
17 Correct 199 ms 2732 KB Output is correct
18 Correct 198 ms 2728 KB Output is correct
19 Correct 238 ms 2720 KB Output is correct
20 Correct 198 ms 2728 KB Output is correct
21 Correct 879 ms 10004 KB Output is correct
22 Correct 872 ms 10004 KB Output is correct
23 Correct 869 ms 9988 KB Output is correct
24 Correct 872 ms 10000 KB Output is correct
25 Correct 899 ms 10000 KB Output is correct
26 Correct 849 ms 10032 KB Output is correct
27 Correct 895 ms 9996 KB Output is correct
28 Correct 870 ms 9992 KB Output is correct
29 Correct 848 ms 9996 KB Output is correct
30 Correct 936 ms 9992 KB Output is correct