oj.uz

Submission #878048

# Submission time Handle Problem Language Result Execution time Memory
878048 2023-11-24T03:36:11 Z noiaint Index (COCI21_index) C++17
110 / 110
 931 ms 14980 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

const int block = 750;

struct query {
    int l, r, id;
    query(int _l = 0, int _r = 0, int _id = 0) {
        l = _l;
        r = _r;
        id = _id;
    }
    bool operator < (const query &a) const {
        return l / block != a.l / block ? l / block < a.l / block : r < a.r;
    }
};

int n, q;
int a[N];
vector<query> queries;
int ans[N];
int bit[N];

void update(int u, int c) {
    for (; u <= n; u += u & (-u)) bit[u] += c;
}
int get(int u) {
    int res = 0;
    for (; u > 0; u -= u & (-u)) res += bit[u];
    return res;
}

void ins(int x) {
    update(x, 1);
}
void del(int x) {
    update(x, -1);
}

int getans(int x) {
    int l = 1, r = n;
    int res = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (mid + get(mid - 1) <= x) {
            res = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return res;
}

void process() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        queries.emplace_back(l, r, i);
    }
    sort(all(queries));
    int L = 1, R = 1;
    ins(a[1]);
    for (auto [l, r, id] : queries) {
        while (L < l) del(a[L++]);
        while (L > l) ins(a[--L]);
        while (R < r) ins(a[++R]);
        while (R > r) del(a[R--]);
        ans[id] = getans(r - l + 1);
    }   

    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;
    
    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 134 ms 7628 KB Output is correct
12 Correct 134 ms 7764 KB Output is correct
13 Correct 134 ms 7624 KB Output is correct
14 Correct 135 ms 7760 KB Output is correct
15 Correct 133 ms 7752 KB Output is correct
16 Correct 132 ms 7760 KB Output is correct
17 Correct 134 ms 7628 KB Output is correct
18 Correct 135 ms 7628 KB Output is correct
19 Correct 133 ms 7876 KB Output is correct
20 Correct 133 ms 7772 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 134 ms 7628 KB Output is correct
12 Correct 134 ms 7764 KB Output is correct
13 Correct 134 ms 7624 KB Output is correct
14 Correct 135 ms 7760 KB Output is correct
15 Correct 133 ms 7752 KB Output is correct
16 Correct 132 ms 7760 KB Output is correct
17 Correct 134 ms 7628 KB Output is correct
18 Correct 135 ms 7628 KB Output is correct
19 Correct 133 ms 7876 KB Output is correct
20 Correct 133 ms 7772 KB Output is correct
21 Correct 903 ms 14404 KB Output is correct
22 Correct 878 ms 14388 KB Output is correct
23 Correct 919 ms 14528 KB Output is correct
24 Correct 931 ms 14392 KB Output is correct
25 Correct 872 ms 14980 KB Output is correct
26 Correct 898 ms 14528 KB Output is correct
27 Correct 871 ms 14856 KB Output is correct
28 Correct 884 ms 14620 KB Output is correct
29 Correct 882 ms 14524 KB Output is correct
30 Correct 878 ms 14372 KB Output is correct