oj.uz

Submission #397616

# Submission time Handle Problem Language Result Execution time Memory
397616 2021-05-02T14:37:29 Z MrRobot_28 Index (COCI21_index) C++17
60 / 110
 2500 ms 121220 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#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 39 ms 56876 KB Output is correct
2 Correct 39 ms 56768 KB Output is correct
3 Correct 39 ms 56780 KB Output is correct
4 Correct 43 ms 56868 KB Output is correct
5 Correct 39 ms 56780 KB Output is correct
6 Correct 39 ms 56772 KB Output is correct
7 Correct 38 ms 56780 KB Output is correct
8 Correct 39 ms 56816 KB Output is correct
9 Correct 39 ms 56888 KB Output is correct
10 Correct 39 ms 56780 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 56876 KB Output is correct
2 Correct 39 ms 56768 KB Output is correct
3 Correct 39 ms 56780 KB Output is correct
4 Correct 43 ms 56868 KB Output is correct
5 Correct 39 ms 56780 KB Output is correct
6 Correct 39 ms 56772 KB Output is correct
7 Correct 38 ms 56780 KB Output is correct
8 Correct 39 ms 56816 KB Output is correct
9 Correct 39 ms 56888 KB Output is correct
10 Correct 39 ms 56780 KB Output is correct
11 Correct 535 ms 71596 KB Output is correct
12 Correct 522 ms 71556 KB Output is correct
13 Correct 528 ms 71600 KB Output is correct
14 Correct 533 ms 71556 KB Output is correct
15 Correct 521 ms 71556 KB Output is correct
16 Correct 532 ms 71504 KB Output is correct
17 Correct 528 ms 71556 KB Output is correct
18 Correct 533 ms 71568 KB Output is correct
19 Correct 527 ms 71568 KB Output is correct
20 Correct 524 ms 71512 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 56876 KB Output is correct
2 Correct 39 ms 56768 KB Output is correct
3 Correct 39 ms 56780 KB Output is correct
4 Correct 43 ms 56868 KB Output is correct
5 Correct 39 ms 56780 KB Output is correct
6 Correct 39 ms 56772 KB Output is correct
7 Correct 38 ms 56780 KB Output is correct
8 Correct 39 ms 56816 KB Output is correct
9 Correct 39 ms 56888 KB Output is correct
10 Correct 39 ms 56780 KB Output is correct
11 Correct 535 ms 71596 KB Output is correct
12 Correct 522 ms 71556 KB Output is correct
13 Correct 528 ms 71600 KB Output is correct
14 Correct 533 ms 71556 KB Output is correct
15 Correct 521 ms 71556 KB Output is correct
16 Correct 532 ms 71504 KB Output is correct
17 Correct 528 ms 71556 KB Output is correct
18 Correct 533 ms 71568 KB Output is correct
19 Correct 527 ms 71568 KB Output is correct
20 Correct 524 ms 71512 KB Output is correct
21 Execution timed out 2584 ms 121220 KB Time limit exceeded
22 Halted 0 ms 0 KB -