Submission #538754

#	Time	Username	Problem	Language	Result	Execution time	Memory
538754		Jomnoi	Index (COCI21_index)	C++17	110 / 110	993 ms	10060 KiB

index

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

const int N = 2e5 + 10;
const int BLOCK_SIZE = 450;

int p[N];
int fenwick[N];
int ans[N];

class QUERY {
public :
    int l, r, i;
    QUERY() : l(0), r(0), i(0) {}
    QUERY(int l_, int r_, int i_) : l(l_), r(r_), i(i_) {}
    bool operator<(const QUERY &o) const {
        return make_pair((l + BLOCK_SIZE - 1) / BLOCK_SIZE, r) < make_pair((o.l + BLOCK_SIZE - 1) / BLOCK_SIZE, o.r);
    }
};

class Fenwick {
public :
    void update(int idx, int v) {
        for(; idx < N; idx += (idx & -idx)) {
            fenwick[idx] += v;
        }
    }

    int query(int idx) {
        int res = 0;
        for(; idx > 0; idx -= (idx & -idx)) {
            res += fenwick[idx];
        }
        return res;
    }
}fw;

int main() {
    int n, q;
    scanf(" %d %d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf(" %d", &p[i]);
    }

    vector <QUERY> query;
    for(int i = 1; i <= q; i++) {
        int l, r;
        scanf(" %d %d", &l, &r);
        query.push_back(QUERY(l, r, i));
    }
    sort(query.begin(), query.end());

    int cur_l = 1, cur_r = 0;
    for(auto [l, r, i] : query) {
        while(cur_l > l) {
            fw.update(p[--cur_l], 1);
        }
        while(cur_r < r) {
            fw.update(p[++cur_r], 1);
        }
        while(cur_l < l) {
            fw.update(p[cur_l++], -1);
        }
        while(cur_r > r) {
            fw.update(p[cur_r--], -1);
        }

        int le = 1, hi = r - l + 1, pos = 1;
        while(le <= hi) {
            int mid = (le + hi) / 2;
            
            if(fw.query(n) - fw.query(mid - 1) < mid) {
                hi = mid - 1;
            }
            else {
                le = mid + 1;
                pos = mid;
            }
        }
        ans[i] = pos;
    }

    for(int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
index.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf(" %d", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~~
index.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf(" %d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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