Submission #1082841

# Submission time Handle Problem Language Result Execution time Memory
1082841 2024-09-01T17:57:31 Z ShaShi Index (COCI21_index) C++17
110 / 110
1500 ms 152148 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 9 ms 13404 KB Output is correct
2 Correct 9 ms 13212 KB Output is correct
3 Correct 9 ms 13400 KB Output is correct
4 Correct 10 ms 13400 KB Output is correct
5 Correct 10 ms 13404 KB Output is correct
6 Correct 9 ms 13400 KB Output is correct
7 Correct 10 ms 13404 KB Output is correct
8 Correct 8 ms 13404 KB Output is correct
9 Correct 9 ms 13444 KB Output is correct
10 Correct 10 ms 13404 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 13404 KB Output is correct
2 Correct 9 ms 13212 KB Output is correct
3 Correct 9 ms 13400 KB Output is correct
4 Correct 10 ms 13400 KB Output is correct
5 Correct 10 ms 13404 KB Output is correct
6 Correct 9 ms 13400 KB Output is correct
7 Correct 10 ms 13404 KB Output is correct
8 Correct 8 ms 13404 KB Output is correct
9 Correct 9 ms 13444 KB Output is correct
10 Correct 10 ms 13404 KB Output is correct
11 Correct 217 ms 44416 KB Output is correct
12 Correct 206 ms 44368 KB Output is correct
13 Correct 227 ms 44312 KB Output is correct
14 Correct 202 ms 44332 KB Output is correct
15 Correct 209 ms 44456 KB Output is correct
16 Correct 203 ms 44416 KB Output is correct
17 Correct 205 ms 44368 KB Output is correct
18 Correct 209 ms 44372 KB Output is correct
19 Correct 204 ms 44468 KB Output is correct
20 Correct 218 ms 44372 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 13404 KB Output is correct
2 Correct 9 ms 13212 KB Output is correct
3 Correct 9 ms 13400 KB Output is correct
4 Correct 10 ms 13400 KB Output is correct
5 Correct 10 ms 13404 KB Output is correct
6 Correct 9 ms 13400 KB Output is correct
7 Correct 10 ms 13404 KB Output is correct
8 Correct 8 ms 13404 KB Output is correct
9 Correct 9 ms 13444 KB Output is correct
10 Correct 10 ms 13404 KB Output is correct
11 Correct 217 ms 44416 KB Output is correct
12 Correct 206 ms 44368 KB Output is correct
13 Correct 227 ms 44312 KB Output is correct
14 Correct 202 ms 44332 KB Output is correct
15 Correct 209 ms 44456 KB Output is correct
16 Correct 203 ms 44416 KB Output is correct
17 Correct 205 ms 44368 KB Output is correct
18 Correct 209 ms 44372 KB Output is correct
19 Correct 204 ms 44468 KB Output is correct
20 Correct 218 ms 44372 KB Output is correct
21 Correct 1355 ms 152028 KB Output is correct
22 Correct 1376 ms 151940 KB Output is correct
23 Correct 1410 ms 152084 KB Output is correct
24 Correct 1423 ms 152148 KB Output is correct
25 Correct 1410 ms 152144 KB Output is correct
26 Correct 1367 ms 152148 KB Output is correct
27 Correct 1403 ms 152144 KB Output is correct
28 Correct 1458 ms 152140 KB Output is correct
29 Correct 1500 ms 152052 KB Output is correct
30 Correct 1398 ms 152024 KB Output is correct