oj.uz

Submission #1110799

# Submission time Handle Problem Language Result Execution time Memory
1110799 2024-11-10T13:50:32 Z whoknow Index (COCI21_index) C++17
60 / 110
 223 ms 48200 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 200005
#define MAXTREE 3600005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, ntest;
int a[MAXN];
namespace sub1
{
int node, MX;
int st[MAXTREE], root[MAXN];
ii child[MAXTREE];
void update(int id, int pre, int l, int r, int u)
{
    if(l == r)
        return st[id]=st[pre]+1, void();
    int mid = (l + r) / 2;
    node++;
    if(u <= mid)
    {
        child[id].F = node;
        child[id].S = child[pre].S;
        update(node, child[pre].F, l, mid, u);
    }
    else
    {
        child[id].F = child[pre].F;
        child[id].S = node;
        update(node, child[pre].S, mid + 1, r, u);
    }
    st[id] = st[child[id].F] + st[child[id].S];
}
int get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u)
        return 0;
    if(l >= u && r <= v)
        return st[id];
    int mid = (l + r) / 2;
    return get(child[id].F, l, mid, u, v) + get(child[id].S, mid + 1, r, u, v);
}
int bina(int L, int R)
{
    int l = 1, r = R - L + 1;
    while(l < r)
    {
        int mid = (l + r+1) / 2;
        if(get(root[R], 1, MX, mid, MX) - get(root[L - 1], 1, MX, mid, MX) >= mid)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
void solve()
{
    MX = *max_element(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
    {
        node++;
        root[i] = node;
        update(node, root[i - 1], 1, MX, a[i]);
    }
//    cout << get(root[n], 1, MX, 1, MX) << endl;
    for(int i = 1; i <= ntest; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << bina(l, r) << endl;
    }
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> ntest;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sub1::solve();
}

Compilation message

index.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main()
      | ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4684 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 3 ms 4856 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 3 ms 4688 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4684 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 3 ms 4856 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 3 ms 4688 KB Output is correct
11 Correct 207 ms 17488 KB Output is correct
12 Correct 200 ms 17988 KB Output is correct
13 Correct 196 ms 17992 KB Output is correct
14 Correct 200 ms 17256 KB Output is correct
15 Correct 195 ms 18044 KB Output is correct
16 Correct 212 ms 18004 KB Output is correct
17 Correct 222 ms 17224 KB Output is correct
18 Correct 198 ms 18264 KB Output is correct
19 Correct 198 ms 18100 KB Output is correct
20 Correct 223 ms 17992 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4684 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 3 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 3 ms 4856 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 3 ms 4688 KB Output is correct
11 Correct 207 ms 17488 KB Output is correct
12 Correct 200 ms 17988 KB Output is correct
13 Correct 196 ms 17992 KB Output is correct
14 Correct 200 ms 17256 KB Output is correct
15 Correct 195 ms 18044 KB Output is correct
16 Correct 212 ms 18004 KB Output is correct
17 Correct 222 ms 17224 KB Output is correct
18 Correct 198 ms 18264 KB Output is correct
19 Correct 198 ms 18100 KB Output is correct
20 Correct 223 ms 17992 KB Output is correct
21 Incorrect 138 ms 48200 KB Output isn't correct
22 Halted 0 ms 0 KB -