oj.uz

Submission #397612

# Submission time Handle Problem Language Result Execution time Memory
397612 2021-05-02T14:30:25 Z MrRobot_28 Index (COCI21_index) C++17
60 / 110
 2500 ms 166428 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define sz(a) (int)a.size()
const int mod = 1e9 + 7;
const int N = 2e5;
vector <int> uk_left[N * 4];
vector <int> uk_right[N * 4];
vector <int> Tree[4 * N];
int h[N];
int n, q;
void build(int v, int l, int r)
{
    if(l == r)
    {
        Tree[v].push_back(h[l]);
        return;
    }
    build(v * 2, l, (r + l) / 2);
    build(v * 2 + 1, (r + l) / 2 + 1, r);
    int j = 0;
    for(int i = 0; i < sz(Tree[v * 2]); i++)
    {
        while(j < sz(Tree[v * 2 + 1]) && Tree[v * 2 + 1][j] < Tree[v * 2][i])
        {
            Tree[v].push_back(Tree[v * 2 + 1][j]);
            j++;
        }
        Tree[v].push_back(Tree[v * 2][i]);
    }
    while(j < sz(Tree[v * 2 + 1]))
    {
        Tree[v].push_back(Tree[v * 2 + 1][j]);
        j++;
    }
    int it1 = sz(Tree[v * 2]), it2 = sz(Tree[v * 2 + 1]);
    uk_left[v].resize(r - l + 1);
    uk_right[v].resize(r - l + 1);
    for(int i = sz(Tree[v]) - 1; i >= 0; i--)
    {
        while(it1 > 0 && Tree[v * 2][it1 - 1] >= Tree[v][i])
        {
            it1--;
        }
        uk_left[v][i] = it1;
        while(it2 > 0 && Tree[v * 2 + 1][it2 - 1] >= Tree[v][i])
        {
            it2--;
        }
        uk_right[v][i] = it2;
    }
}
int go_to(int v, int l, int r, int al, int ar, int uk)
{
    if(r < al || l > ar)
    {
        return 0;
    }
    if(uk == sz(Tree[v]))
    {
        return 0;
    }
    if(l >= al && r <= ar)
    {
        return r - l + 1 - uk;
    }
    return go_to(v * 2, l, (r + l) / 2, al, ar, uk_left[v][uk]) + go_to(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, uk_right[v][uk]);
}
int q_ans(int l, int r, int x)
{
    int l1 = -1, r1 = sz(Tree[1]);
    while(r1 - l1 > 1)
    {
        int midd = (r1 + l1) / 2;
        if(Tree[1][midd] < x)
        {
            l1 = midd;
        }
        else
        {
            r1 = midd;
        }
    }
    return go_to(1, 0, n - 1, l, r, r1);
}
signed main()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    build(1, 0, n - 1);
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int l1 = 1, r1 = r - l + 2;
        while(r1 - l1 > 1)
        {
            int midd = (r1 + l1) / 2;
            if(q_ans(l, r, midd) >= midd)
            {
                l1 = midd;
            }
            else
            {
                r1 = midd;
            }
        }
        cout << l1 << "\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 56908 KB Output is correct
2 Correct 40 ms 56904 KB Output is correct
3 Correct 39 ms 56968 KB Output is correct
4 Correct 40 ms 57012 KB Output is correct
5 Correct 40 ms 56964 KB Output is correct
6 Correct 40 ms 56904 KB Output is correct
7 Correct 40 ms 56940 KB Output is correct
8 Correct 38 ms 56940 KB Output is correct
9 Correct 45 ms 57012 KB Output is correct
10 Correct 40 ms 56908 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 56908 KB Output is correct
2 Correct 40 ms 56904 KB Output is correct
3 Correct 39 ms 56968 KB Output is correct
4 Correct 40 ms 57012 KB Output is correct
5 Correct 40 ms 56964 KB Output is correct
6 Correct 40 ms 56904 KB Output is correct
7 Correct 40 ms 56940 KB Output is correct
8 Correct 38 ms 56940 KB Output is correct
9 Correct 45 ms 57012 KB Output is correct
10 Correct 40 ms 56908 KB Output is correct
11 Correct 582 ms 81792 KB Output is correct
12 Correct 567 ms 81724 KB Output is correct
13 Correct 575 ms 81632 KB Output is correct
14 Correct 575 ms 81832 KB Output is correct
15 Correct 573 ms 81848 KB Output is correct
16 Correct 586 ms 81660 KB Output is correct
17 Correct 577 ms 81744 KB Output is correct
18 Correct 576 ms 81632 KB Output is correct
19 Correct 587 ms 81716 KB Output is correct
20 Correct 573 ms 81632 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 56908 KB Output is correct
2 Correct 40 ms 56904 KB Output is correct
3 Correct 39 ms 56968 KB Output is correct
4 Correct 40 ms 57012 KB Output is correct
5 Correct 40 ms 56964 KB Output is correct
6 Correct 40 ms 56904 KB Output is correct
7 Correct 40 ms 56940 KB Output is correct
8 Correct 38 ms 56940 KB Output is correct
9 Correct 45 ms 57012 KB Output is correct
10 Correct 40 ms 56908 KB Output is correct
11 Correct 582 ms 81792 KB Output is correct
12 Correct 567 ms 81724 KB Output is correct
13 Correct 575 ms 81632 KB Output is correct
14 Correct 575 ms 81832 KB Output is correct
15 Correct 573 ms 81848 KB Output is correct
16 Correct 586 ms 81660 KB Output is correct
17 Correct 577 ms 81744 KB Output is correct
18 Correct 576 ms 81632 KB Output is correct
19 Correct 587 ms 81716 KB Output is correct
20 Correct 573 ms 81632 KB Output is correct
21 Execution timed out 2593 ms 166428 KB Time limit exceeded
22 Halted 0 ms 0 KB -