Submission #518312

#	Time	Username	Problem	Language	Result	Execution time	Memory
518312		Vimmer	Index (COCI21_index)	C++14	110 / 110	835 ms	10056 KiB

index

#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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50