oj.uz

Submission #878047

# Submission time Handle Problem Language Result Execution time Memory
878047 2023-11-24T03:35:53 Z noiaint Index (COCI21_index) C++17
110 / 110
 443 ms 90856 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;
}

int n, q;
int a[N];
pair<int, int> query[N];
vector<int> pos[N], v[N];
int l[N], r[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;
}
int get(int l, int r) {
    return get(r) - get(l - 1);
}

void process() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= q; ++i) {
        cin >> query[i].fi >> query[i].se;
        l[i] = 1, r[i] = n + 1;
    }
    while (true) {
        bool ok = true;
        for (int i = 1; i <= q; ++i) {
            if (l[i] <= r[i]) v[(l[i] + r[i]) / 2].push_back(i);
            if (r[i] - l[i] > 1) ok = false;
        }
        if (ok) break;
        
        memset(bit, 0, sizeof bit);
        for (int i = n; i >= 1; --i) {
            for (int j : pos[i]) update(j, 1);
            for (int id : v[i]) {
                if (get(query[id].fi, query[id].se) >= i) l[id] = i;
                else r[id] = i;
            }
            v[i].clear();
        }
    }

    for (int i = 1; i <= q; ++i) cout << l[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 18 ms 57944 KB Output is correct
2 Correct 13 ms 57944 KB Output is correct
3 Correct 13 ms 58080 KB Output is correct
4 Correct 13 ms 57948 KB Output is correct
5 Correct 14 ms 58172 KB Output is correct
6 Correct 13 ms 58200 KB Output is correct
7 Correct 13 ms 58036 KB Output is correct
8 Correct 13 ms 57948 KB Output is correct
9 Correct 13 ms 58088 KB Output is correct
10 Correct 13 ms 58196 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57944 KB Output is correct
2 Correct 13 ms 57944 KB Output is correct
3 Correct 13 ms 58080 KB Output is correct
4 Correct 13 ms 57948 KB Output is correct
5 Correct 14 ms 58172 KB Output is correct
6 Correct 13 ms 58200 KB Output is correct
7 Correct 13 ms 58036 KB Output is correct
8 Correct 13 ms 57948 KB Output is correct
9 Correct 13 ms 58088 KB Output is correct
10 Correct 13 ms 58196 KB Output is correct
11 Correct 83 ms 63940 KB Output is correct
12 Correct 79 ms 63956 KB Output is correct
13 Correct 79 ms 63960 KB Output is correct
14 Correct 79 ms 64052 KB Output is correct
15 Correct 84 ms 64224 KB Output is correct
16 Correct 79 ms 63912 KB Output is correct
17 Correct 79 ms 63904 KB Output is correct
18 Correct 79 ms 64008 KB Output is correct
19 Correct 80 ms 63944 KB Output is correct
20 Correct 84 ms 63884 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57944 KB Output is correct
2 Correct 13 ms 57944 KB Output is correct
3 Correct 13 ms 58080 KB Output is correct
4 Correct 13 ms 57948 KB Output is correct
5 Correct 14 ms 58172 KB Output is correct
6 Correct 13 ms 58200 KB Output is correct
7 Correct 13 ms 58036 KB Output is correct
8 Correct 13 ms 57948 KB Output is correct
9 Correct 13 ms 58088 KB Output is correct
10 Correct 13 ms 58196 KB Output is correct
11 Correct 83 ms 63940 KB Output is correct
12 Correct 79 ms 63956 KB Output is correct
13 Correct 79 ms 63960 KB Output is correct
14 Correct 79 ms 64052 KB Output is correct
15 Correct 84 ms 64224 KB Output is correct
16 Correct 79 ms 63912 KB Output is correct
17 Correct 79 ms 63904 KB Output is correct
18 Correct 79 ms 64008 KB Output is correct
19 Correct 80 ms 63944 KB Output is correct
20 Correct 84 ms 63884 KB Output is correct
21 Correct 414 ms 90620 KB Output is correct
22 Correct 439 ms 90552 KB Output is correct
23 Correct 403 ms 90568 KB Output is correct
24 Correct 399 ms 90568 KB Output is correct
25 Correct 443 ms 90856 KB Output is correct
26 Correct 395 ms 90376 KB Output is correct
27 Correct 402 ms 90492 KB Output is correct
28 Correct 416 ms 90496 KB Output is correct
29 Correct 389 ms 90524 KB Output is correct
30 Correct 411 ms 90428 KB Output is correct