Submission #1082841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082841		ShaShi	Index (COCI21_index)	C++17	110 / 110	1500 ms	152148 KiB

index

#include <bits/stdc++.h>
 
// #define int long long
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
 
const int MAXN = (int)2e5 + 7;
const int MOD = 998244353;
const int INF = (int)1e9 + 7;

 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], h[MAXN], res[MAXN];
vector<int> vec[MAXN];


/* Presistent SegTree */
#define mid ((l+r)>>1)


struct Node {
    int val; Node *l, *r;

    Node(int x) {
        val = x; l = r = NULL;
    }

    Node(Node *ll, Node *rr) {
        l = ll; r = rr;
        if (l) val += l->val;
        if (r) val += r->val;
    }

    Node(Node *node) {
        val = node->val; l = node->l; r = node->r;
    }
};


Node *build(int l=0, int r=n) {
    if (l+1 == r) return new Node(0);
    return new Node(build(l, mid), build(mid, r));
}


Node *upd(Node *node, int ind, int l=0, int r=n) {
    if (l+1 == r) return new Node((node->val)+1);
    if (ind < mid) return new Node(upd(node->l, ind, l, mid), node->r);
    return new Node(node->l, upd(node->r, ind, mid, r));
}


int get(Node *node, int s, int t, int l=0, int r=n) {
    if (s >= t) return 0;
    if (s <= l && t >= r) return node->val;
    if (t <= mid) return get(node->l, s, t, l, mid);
    if (s >= mid) return get(node->r, s, t, mid, r);
    return get(node->l, s, t, l, mid)+get(node->r, s, t, mid, r);
}

/* Presistent SegTree */


Node *seg[MAXN];


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> q;

    for (int i=1; i<=n; i++) {
        cin >> arr[i];

        vec[arr[i]].pb(i);
    }

    seg[0] = build();

    for (int i=1; i<MAXN; i++) {
        seg[i] = new Node(seg[i-1]);

        for (int u:vec[i]) seg[i] = upd(seg[i], u-1);
    }

    while (q--) {
        cin >> u >> v;

        int l = 1, r = v-u+2;

        while (r-l > 1) {
            if (v-u+1-get(seg[mid-1], u-1, v) >= mid) l = mid;
            else r = mid;
        }

        cout << l << endl;
    }
    
    return 0;
}

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