Submission #890133

#	Time	Username	Problem	Language	Result	Execution time	Memory
890133		Namviet2704	Index (COCI21_index)	C++17	110 / 110	848 ms	57076 KiB

index

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int N = 2e5 + 2;
const int M = 2e5;;

int n, q, a[N];

struct Query
{
    int l, k, pos;
};

vector<Query> ask[N];

struct Node
{
    int left, right; // ID of left child & right child
    int sum;         // Max value of node
    Node() {}
    Node(int sum, int left, int right) : sum(sum), left(left), right(right) {}
} it[11000111]; // Each node has a position in this array, called ID

int nNode, ver[N];

inline void refine(int cur)
{
    it[cur].sum = (it[it[cur].left].sum + it[it[cur].right].sum);
}

// Update a range, and return new ID of node
int update(int l, int r, int u, int oldId)
{
    if (l == r)
    {
        it[nNode + 1] = Node(it[oldId].sum + 1, 0, 0);
        ++nNode;
        return nNode;
    }

    int mid = (l + r) >> 1;
    int cur = ++nNode;

    if (u <= mid)
    {
        it[cur].left = update(l, mid, u, it[oldId].left);
        it[cur].right = it[oldId].right;
        refine(cur);
    }
    else
    {
        it[cur].left = it[oldId].left;
        it[cur].right = update(mid + 1, r, u, it[oldId].right);
        refine(cur);
    }

    return cur;
}

int get(int nodeId, int l, int r, int u, int v)
{
    if (nodeId == 0)
        return 0;
    if (v < l || r < u)
        return 0;
    if (u <= l && r <= v)
        return it[nodeId].sum;
    int mid = (l + r) >> 1;
    return (get(it[nodeId].left, l, mid, u, v) + get(it[nodeId].right, mid + 1, r, u, v));
}

int main()
{
    // freopen(task ".inp", "r", stdin);
    // freopen(task ".out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        ver[i] = update(1, M, a[i], ver[i - 1]);
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        int low = 1, high = n, mid, tmp = 0;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (get(ver[r], 1, M, mid, M) - get(ver[l - 1], 1, M, mid, M) >= mid)
            {
                tmp = mid;
                low = mid + 1;
            }
            else
                high = mid - 1;
        }
        cout << tmp << '\n';
    }
    return 0;
}

Compilation message (stderr)

index.cpp: In constructor 'Node::Node(int, int, int)':
index.cpp:22:9: warning: 'Node::sum' will be initialized after [-Wreorder]
   22 |     int sum;         // Max value of node
      |         ^~~
index.cpp:21:9: warning:   'int Node::left' [-Wreorder]
   21 |     int left, right; // ID of left child & right child
      |         ^~~~
index.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Node(int sum, int left, int right) : sum(sum), left(left), right(right) {}
      |     ^~~~

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