oj.uz

Submission #518312

# Submission time Handle Problem Language Result Execution time Memory
518312 2022-01-23T11:08:29 Z Vimmer Index (COCI21_index) C++14
110 / 110
 835 ms 10056 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
#define N 200001
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

int ans[N], l[N], r[N];

const int BL = 450;

int l1, l2;

bool cmp(int &x, int &y)
{
    l1 = l[x] / BL;

    l2 = l[y] / BL;

    if (l1 != l2)
        return l1 < l2;

    if (l1 & 1)
        return r[x] > r[y];

    return r[x] < r[y];
}

const int NN = 200001;

int t[NN];

void add(int v)
{
    for (; v < NN; v = v | (v + 1))
        t[v]++;
}

void del(int v)
{
    for (; v < NN; v = v | (v + 1))
        t[v]--;
}

int res;

void get(int v)
{
    res = 0;

    for (; v >= 0; v = (v & (v + 1)) - 1)
        res += t[v];
}

int main()
{
    istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    int n, q, i;

    cin >> n >> q;

    int a[n];

    for (i = 0; i < n; i++)
        cin >> a[i];

    vector <int> vr; vr.clear();

    for (i = 0; i < q; i++)
    {
        cin >> l[i] >> r[i];

        l[i]--; r[i]--;

        vr.PB(i);
    }

    sort(all(vr), cmp);

    int ll = 0, rr = -1, all, L, R, md;

    for (i = 0; i < sz(vr); i++)
    {
        while (rr < r[vr[i]])
            add(a[++rr]);

        while (l[vr[i]] < ll)
            add(a[--ll]);

        while (r[vr[i]] < rr)
            del(a[rr--]);

        while (ll < l[vr[i]])
            del(a[ll++]);

        all = rr - ll + 1;

        L = 0; R = all;

        while (L < R)
        {
            md = (L + R + 1) >> 1;

            get(md - 1);

            if (all - res >= md)
                L = md;
                    else R = md - 1;
        }

        ans[vr[i]] = L;
    }

    for (i = 0; i < q; i++)
        pri(ans[i]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 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 10 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 168 ms 2720 KB Output is correct
12 Correct 170 ms 2724 KB Output is correct
13 Correct 165 ms 2668 KB Output is correct
14 Correct 173 ms 2764 KB Output is correct
15 Correct 175 ms 2724 KB Output is correct
16 Correct 171 ms 2736 KB Output is correct
17 Correct 177 ms 2724 KB Output is correct
18 Correct 176 ms 2724 KB Output is correct
19 Correct 166 ms 2716 KB Output is correct
20 Correct 172 ms 2712 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 168 ms 2720 KB Output is correct
12 Correct 170 ms 2724 KB Output is correct
13 Correct 165 ms 2668 KB Output is correct
14 Correct 173 ms 2764 KB Output is correct
15 Correct 175 ms 2724 KB Output is correct
16 Correct 171 ms 2736 KB Output is correct
17 Correct 177 ms 2724 KB Output is correct
18 Correct 176 ms 2724 KB Output is correct
19 Correct 166 ms 2716 KB Output is correct
20 Correct 172 ms 2712 KB Output is correct
21 Correct 803 ms 10056 KB Output is correct
22 Correct 783 ms 10016 KB Output is correct
23 Correct 835 ms 9988 KB Output is correct
24 Correct 770 ms 9992 KB Output is correct
25 Correct 811 ms 9996 KB Output is correct
26 Correct 827 ms 9992 KB Output is correct
27 Correct 833 ms 9988 KB Output is correct
28 Correct 784 ms 9988 KB Output is correct
29 Correct 763 ms 10044 KB Output is correct
30 Correct 800 ms 9996 KB Output is correct