oj.uz

Submission #890133

# Submission time Handle Problem Language Result Execution time Memory
890133 2023-12-20T15:23:55 Z Namviet2704 Index (COCI21_index) C++17
110 / 110
 848 ms 57076 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5900 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 3 ms 5720 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 3 ms 5780 KB Output is correct
10 Correct 3 ms 5976 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5900 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 3 ms 5720 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 3 ms 5780 KB Output is correct
10 Correct 3 ms 5976 KB Output is correct
11 Correct 173 ms 18784 KB Output is correct
12 Correct 172 ms 18776 KB Output is correct
13 Correct 171 ms 18820 KB Output is correct
14 Correct 173 ms 18772 KB Output is correct
15 Correct 173 ms 18792 KB Output is correct
16 Correct 171 ms 19028 KB Output is correct
17 Correct 174 ms 18820 KB Output is correct
18 Correct 167 ms 19012 KB Output is correct
19 Correct 169 ms 18688 KB Output is correct
20 Correct 166 ms 18612 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct
4 Correct 3 ms 5900 KB Output is correct
5 Correct 3 ms 5720 KB Output is correct
6 Correct 3 ms 5720 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5724 KB Output is correct
9 Correct 3 ms 5780 KB Output is correct
10 Correct 3 ms 5976 KB Output is correct
11 Correct 173 ms 18784 KB Output is correct
12 Correct 172 ms 18776 KB Output is correct
13 Correct 171 ms 18820 KB Output is correct
14 Correct 173 ms 18772 KB Output is correct
15 Correct 173 ms 18792 KB Output is correct
16 Correct 171 ms 19028 KB Output is correct
17 Correct 174 ms 18820 KB Output is correct
18 Correct 167 ms 19012 KB Output is correct
19 Correct 169 ms 18688 KB Output is correct
20 Correct 166 ms 18612 KB Output is correct
21 Correct 844 ms 56476 KB Output is correct
22 Correct 823 ms 56916 KB Output is correct
23 Correct 827 ms 56620 KB Output is correct
24 Correct 835 ms 57076 KB Output is correct
25 Correct 829 ms 56404 KB Output is correct
26 Correct 815 ms 56740 KB Output is correct
27 Correct 848 ms 56468 KB Output is correct
28 Correct 815 ms 56552 KB Output is correct
29 Correct 838 ms 56428 KB Output is correct
30 Correct 807 ms 56824 KB Output is correct