Submission #538746

#	Time	Username	Problem	Language	Result	Execution time	Memory
538746		Jomnoi	Index (COCI21_index)	C++17	60 / 110	2582 ms	147192 KiB

index

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

const int N = 2e5 + 10;

vector <int> idx_paper[N];

class Node {
public :
    int sum;
    Node *l, *r;
    Node(const int &s) : sum(s), l(NULL), r(NULL) {}
    Node(Node *L, Node *R) : sum(0), l(L), r(R) {
        if(L != NULL) {
            sum += L->sum;
        }
        if(R != NULL) {
            sum += R->sum;
        }
    }
    Node(Node *copy) : sum(copy->sum), l(copy->l), r(copy->r) {}
};
Node *root[N];

Node *build(const int &l, const int &r) {
    if(l == r) {
        return new Node(0);
    }

    int mid = (l + r) / 2;
    return new Node(build(l, mid), build(mid + 1, r));
}

Node *update(Node *node, const int &l, const int &r, const int &q) {
    if(l == r) {
        return new Node(1);
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return new Node(update(node->l, l, mid, q), node->r);
    }
    return new Node(node->l, update(node->r, mid + 1, r, q));
}

int query(Node *node, const int &l, const int &r, const int &ql, const int &qr) {
    if(r < ql or qr < l) {
        return 0;
    }
    if(ql <= l and r <= qr) {
        return node->sum;
    }

    int mid = (l + r) / 2;
    return query(node->l, l, mid, ql, qr) + query(node->r, mid + 1, r, ql, qr);
}

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

    root[n + 1] = build(1, n);
    for(int i = n; i >= 1; i--) {
        root[i] = new Node(root[i + 1]);
        for(auto idx : idx_paper[i]) {
            root[i] = update(root[i], 1, n, idx);
        }
    }

    while(q--) {
        int a, b;
        scanf(" %d %d", &a, &b);

        int range = b - a + 1;
        int l = 1, r = range, pos = 1;
        while(l <= r) {
            int mid = (l + r) / 2;

            if(query(root[mid], 1, n, a, b) < mid) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
                pos = mid;
            }
        }
        printf("%d\n", pos);
    }
    return 0;
}

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
index.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %d", &p);
      |         ~~~~~^~~~~~~~~~~
index.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf(" %d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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