oj.uz

Submission #781360

# Submission time Handle Problem Language Result Execution time Memory
781360 2023-07-13T04:27:13 Z ZHIRDILBILDIZ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
13 / 100
 1006 ms 186940 KB 
#include<bits/stdc++.h>
using namespace std ;
const int N = (1 << 20) ;
map<int, int> sum ;
int n, m, all_mn = 1e9, a[N + 1], ind[N + 1], pw[N + 1], mn1[N + 1][21], mn2[N + 1][21] ;
void build_sparce_table1()
{
    mn1[1][0] = a[1] ;
    for(int i = 2 ; i <= N ; i++)
        pw[i] = pw[i / 2] + 1, mn1[i][0] = a[i] ;
    for(int i = 1 ; i < 21 ; i++)
        for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
            mn1[j][i] = min(mn1[j][i - 1], mn1[j + (1 << (i - 1))][i - 1]) ;
}
int get_min1(int l, int r)
{
    int num = pw[r - l + 1] ;
    return min(mn1[l][num], mn1[r - (1 << num) + 1][num]) ;
}
void build_sparce_table2()
{
    mn2[1][0] = ind[1] ;
    for(int i = 2 ; i <= N ; i++)
        mn2[i][0] = ind[i] ;
    for(int i = 1 ; i < 21 ; i++)
        for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
            mn2[j][i] = min(mn2[j][i - 1], mn2[j + (1 << (i - 1))][i - 1]) ;
}
int get_min2(int l, int r)
{
    int num = pw[r - l + 1] ;
    return min(mn2[l][num], mn2[r - (1 << num) + 1][num]) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i], all_mn = min(all_mn, a[i]) ;
    if(n <= 500 && m <= 500)
    {
        int b[n + 1], c[n + 1] ;
        while(m--)
        {
            for(int i = 1 ; i <= n ; i++)
                b[i] = a[i], c[i] = a[i] ;
            int l, r, k, sum = 0 ;
            cin >> l >> r >> k ;
            sort(b + l, b + r + 1) ;
            for(int i = l ; i <= r ; i++)
            {
                int index = i ;
                for(int j = l ; j <= r ; j++)
                    if(c[j] == b[i]){index = j ; break ;}
                for(int q = index ; q > i ; q--)
                    swap(c[q], c[q - 1]), sum = max(sum, c[q] + c[q - 1]) ;
            }
            if(sum <= k)cout << "1\n" ;
            else cout << "0\n" ;
        }
        return 0 ;
    }
    if(n <= 5e3 && m <= 5e3)
    {
        return 0 ;
    }
    build_sparce_table1() ;
    for(int i = 1 ; i <= N ; i++)
    {
        int l = i, r = N + 1 ;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1 ;
            if(get_min1(i, mid) < a[i])r = mid ;
            else l = mid ;
        }
        ind[i] = r ;
    }
    build_sparce_table2() ;
    while(m--)
    {
        int l, r, k ;
        cin >> l >> r >> k ;
        if(l == r || get_min2(l, r - 1) > r)cout << "1\n" ;
        else cout << "0\n" ;
    }
    return 0 ;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Correct 18 ms 332 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Correct 18 ms 332 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 186932 KB Output is correct
2 Correct 893 ms 186768 KB Output is correct
3 Correct 853 ms 186788 KB Output is correct
4 Correct 1006 ms 186832 KB Output is correct
5 Correct 834 ms 186940 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 425 ms 182016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Correct 18 ms 332 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 22 ms 340 KB Output is correct
8 Correct 18 ms 332 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -