Submission #1167445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167445		sunflower	Index (COCI21_index)	C++17	110 / 110	460 ms	38728 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n, q;

#define MAX_N 200'200
int a[MAX_N + 2];

struct Query {
    int l, r;
    void input() {
        cin >> l >> r;
    }
} query[MAX_N + 2];

namespace subtask1 {
    bool check() {
        return (n <= int(1e4));
    }

    struct MST {
        vector <int> seg[4 * MAX_N + 2];

        vector <int> Merge(const vector <int> &a, const vector <int> &b) {
            vector <int> res;
            int i = 0, j = 0;
            while (i < SZ(a) && j < SZ(b)) {
                if (a[i] <= b[j]) {
                    res.push_back(a[i++]);
                } else {
                    res.push_back(b[j++]);
                }
            }

            while (i < SZ(a)) res.push_back(a[i++]);
            while (j < SZ(b)) res.push_back(b[j++]);

            return res;
        }

        void build(int id, int l, int r) {
            if (l == r) {
                seg[id].push_back(a[l]);
                return;
            }

            int g = (l + r) >> 1;
            build(id << 1, l, g);
            build(id << 1 | 1, g + 1, r);
            seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
        }

        int get(int id, int l, int r, int u, int v, const int &value) {
            if (l > v || u > r) return 0;
            if (u <= l && r <= v) {

                int lef = 0, rig = SZ(seg[id]) - 1, g, vt = -1;
                while (lef <= rig) {
                    g = (lef + rig) >> 1;
                    if (seg[id][g] >= value) vt = g, rig = g - 1;
                    else lef = g + 1;
                }

                if (vt == -1) return 0;
                return SZ(seg[id]) - vt;
            }

            int g = (l + r) >> 1;
            return get(id << 1, l, g, u, v, value) + get(id << 1 | 1, g + 1, r, u, v, value);
        }
    } st;

    void solve() {
        st.build(1, 1, n);

        while (q--) {
            int L, R;
            cin >> L >> R;
            int l = 1, r = R - L + 1, g, vt = -1;
            while (l <= r) {
                g = (l + r) >> 1;
                if (st.get(1, 1, n, L, R, g) >= g) vt = g, l = g + 1;
                else r = g - 1;
            }

            if (vt == -1) vt = 0;

            cout << vt << "\n";
        }
    }
};

namespace subtask2 {
    int ans[MAX_N + 2];
    int l[MAX_N + 2], r[MAX_N + 2], value[MAX_N + 2];
    vector <pair <int, int>> queries[MAX_N + 2];

    struct BIT {
        int bit[MAX_N + 2];
        int lim;

        void init(int _n) {
            lim = _n + 1;
            FOR(i, 1, _n + 1) bit[i] = 0;
        }

        void update(int x, int v) {
            for (; x <= lim; x += x & (-x)) bit[x] += v;
        }

        int get(int x) {
            int ans = 0;
            for (; x > 0; x -= x & (-x)) ans += bit[x];

            return ans;
        }

        int calc(int l, int r) {
            if (l > r) return 0;
            return get(r) - get(l - 1);
        }
    } fen;

    vector <bool> calc(const vector <int> &vec) {
        int lim = *max_element(a + 1, a + 1 + n) + 2;
        FOR(i, 0, n) queries[i].clear(), value[i] = 0;

        fen.init(lim);
        // build query;
        for (int id : vec) {
            queries[ query[id].l - 1 ].push_back({id, -1});
            queries[ query[id].r ].push_back({id, 1});
        }

        FOR(i, 1, n) {
            fen.update(a[i], 1);

            for (auto it : queries[i]) {
                int id = it.fi, mul = it.se;
                int mid = (l[id] + r[id]) >> 1;
                value[id] += mul * fen.calc(mid, lim);
            }
        }

        vector <bool> res;
        for (int id : vec) {
            int mid = (l[id] + r[id]) >> 1;
            res.push_back(value[id] >= mid);
        }

        return res;
    }

    void solve() {
        FOR(i, 1, q) query[i].input();

        FOR(i, 1, q) ans[i] = -1;

        vector <int> checks;
        FOR(i, 1, q) {
            checks.push_back(i);
            l[i] = 1, r[i] = query[i].r - query[i].l + 1;
        }

        while (true) {
            vector <bool> results = calc(checks);

            vector <int> tmp;
            for (int i = 0; i < SZ(checks); ++i) {
                int id = checks[i], mid = (l[id] + r[id]) >> 1;
                if (results[i]) ans[id] = mid, l[id] = mid + 1;
                else r[id] = mid - 1;

                if (l[id] <= r[id]) tmp.push_back(id);
            }

            checks = tmp;
            if (checks.empty()) break;
        }

        FOR(i, 1, q) cout << (~ans[i] ? ans[i] : 0) << "\n";
    }
};

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    if (fopen("test.inp","r")) {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }

    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

//    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    subtask2 :: solve();

    return 0;
}

/* Discipline - Calm */

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:215:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
index.cpp:216:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50