oj.uz

Submission #1110800

# Submission time Handle Problem Language Result Execution time Memory
1110800 2024-11-10T13:52:41 Z whoknow Index (COCI21_index) C++17
110 / 110
 1368 ms 53684 KB 
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 200005
#define MAXTREE 4000005
#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()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    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()
      | ^~~~
index.cpp: In function 'int main()':
index.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 3 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 192 ms 15432 KB Output is correct
12 Correct 190 ms 15432 KB Output is correct
13 Correct 193 ms 15504 KB Output is correct
14 Correct 197 ms 15432 KB Output is correct
15 Correct 200 ms 15432 KB Output is correct
16 Correct 199 ms 15432 KB Output is correct
17 Correct 202 ms 15504 KB Output is correct
18 Correct 213 ms 15432 KB Output is correct
19 Correct 220 ms 15432 KB Output is correct
20 Correct 198 ms 15432 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2384 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 3 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 192 ms 15432 KB Output is correct
12 Correct 190 ms 15432 KB Output is correct
13 Correct 193 ms 15504 KB Output is correct
14 Correct 197 ms 15432 KB Output is correct
15 Correct 200 ms 15432 KB Output is correct
16 Correct 199 ms 15432 KB Output is correct
17 Correct 202 ms 15504 KB Output is correct
18 Correct 213 ms 15432 KB Output is correct
19 Correct 220 ms 15432 KB Output is correct
20 Correct 198 ms 15432 KB Output is correct
21 Correct 1250 ms 49644 KB Output is correct
22 Correct 1368 ms 53396 KB Output is correct
23 Correct 1109 ms 53272 KB Output is correct
24 Correct 1078 ms 53452 KB Output is correct
25 Correct 1014 ms 49596 KB Output is correct
26 Correct 1223 ms 53684 KB Output is correct
27 Correct 1195 ms 53476 KB Output is correct
28 Correct 1245 ms 53320 KB Output is correct
29 Correct 1189 ms 53312 KB Output is correct
30 Correct 1243 ms 49808 KB Output is correct