Submission #857390

#	Time	Username	Problem	Language	Result	Execution time	Memory
857390		sleepntsheep	Index (COCI21_index)	C++17	110 / 110	1396 ms	134976 KiB

index

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 200005
#define ALL(x) x.begin(), x.end()

struct node
{
    node *l, *r;
    int a;
    node(int b) : a(b), l(nullptr), r(nullptr) {}
    node (node *l_, node *r_) : l(l_), r(r_), a((l_?l_->a:0) + (r_?r_->a:0)) {}
};

node *build(int l, int r)
{
    if (l == r) return new node(0);
    return new node(build(l, (l+r)/2), build((l+r)/2+1, r));
}

node *upd(node *v, int l, int r, int p)
{
    if (l == r) return new node(v->a + 1);
    if (p <= (l+r)/2) return new node(upd(v->l, l, (l+r)/2, p), v->r);
    return new node(v->l, upd(v->r, (l+r)/2+1, r, p));
}

int count(node *vl, node *vr, int l, int r, int x, int y)
{
    if (y < l || r < x) return 0;
    if (x <= l && r <= y) return vr->a - vl->a;
    return count(vl->l, vr->l, l, (l+r)/2, x, y) + count(vl->r, vr->r, (l+r)/2+1, r, x, y);
}

int n, q;
node *root[N];

int main()
{
    scanf("%d%d", &n, &q);
    root[0] = build(1, n);
    for (int x, i = 1; i <= n; ++i)
        scanf("%d", &x), root[i] = upd(root[i-1], 1, n, x);

    for (int x, y; q--;)
    {
        scanf("%d%d", &x, &y);
        int l = 0, r = y-x+1, z = -1;
        while (l <= r)
        {
            int m = (l+r)/2;
            if (count(root[x-1], root[y], 1, n, m, n) < m)
                r = m - 1;
            else
                z = m, l = m + 1;
        }

        printf("%d\n", z);
    }

    return 0;
}

Compilation message (stderr)

index.cpp: In constructor 'node::node(int)':
index.cpp:21:9: warning: 'node::a' will be initialized after [-Wreorder]
   21 |     int a;
      |         ^
index.cpp:20:11: warning:   'node* node::l' [-Wreorder]
   20 |     node *l, *r;
      |           ^
index.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     node(int b) : a(b), l(nullptr), r(nullptr) {}
      |     ^~~~
index.cpp: In function 'int main()':
index.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
index.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d", &x), root[i] = upd(root[i-1], 1, n, x);
      |         ~~~~~^~~~~~~~~~
index.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

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