oj.uz

Submission #537832

# Submission time Handle Problem Language Result Execution time Memory
537832 2022-03-15T16:21:28 Z N1NT3NDO Index (COCI21_index) C++14
110 / 110
 966 ms 6388 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 = 500;
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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 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 340 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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 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 340 KB Output is correct
11 Correct 226 ms 1908 KB Output is correct
12 Correct 242 ms 1888 KB Output is correct
13 Correct 215 ms 1908 KB Output is correct
14 Correct 224 ms 1908 KB Output is correct
15 Correct 235 ms 1904 KB Output is correct
16 Correct 206 ms 1908 KB Output is correct
17 Correct 217 ms 1908 KB Output is correct
18 Correct 231 ms 1920 KB Output is correct
19 Correct 218 ms 1916 KB Output is correct
20 Correct 215 ms 1908 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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 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 340 KB Output is correct
11 Correct 226 ms 1908 KB Output is correct
12 Correct 242 ms 1888 KB Output is correct
13 Correct 215 ms 1908 KB Output is correct
14 Correct 224 ms 1908 KB Output is correct
15 Correct 235 ms 1904 KB Output is correct
16 Correct 206 ms 1908 KB Output is correct
17 Correct 217 ms 1908 KB Output is correct
18 Correct 231 ms 1920 KB Output is correct
19 Correct 218 ms 1916 KB Output is correct
20 Correct 215 ms 1908 KB Output is correct
21 Correct 966 ms 6328 KB Output is correct
22 Correct 932 ms 6292 KB Output is correct
23 Correct 936 ms 6340 KB Output is correct
24 Correct 906 ms 6292 KB Output is correct
25 Correct 896 ms 6388 KB Output is correct
26 Correct 905 ms 6328 KB Output is correct
27 Correct 906 ms 6292 KB Output is correct
28 Correct 953 ms 6292 KB Output is correct
29 Correct 934 ms 6288 KB Output is correct
30 Correct 929 ms 6292 KB Output is correct