oj.uz

Submission #781579

# Submission time Handle Problem Language Result Execution time Memory
781579 2023-07-13T08:17:06 Z ZHIRDILBILDIZ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 934 ms 223408 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std ;
const int N = (1 << 20) ;
bool ans[N + 1] ;
int n, m, all_mx, all_mn = 1e9, pos[1001], a[N + 1], l[N + 1], r[N + 1], k[N + 1], ind[N + 1], pw[N + 1], mx[N + 1][21], mn1[N + 1][21], mn2[N + 1][21] ;
vector<int> qr[N + 1] ;
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]) ;
}
void build_sparce_table3()
{
    mx[1][0] = a[1] ;
    for(int i = 2 ; i <= N ; i++)
        mx[i][0] = a[i] ;
    for(int i = 1 ; i < 21 ; i++)
        for(int j = 1 ; j <= N - (1 << i) + 1 ; j++)
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]) ;
}
int get_max(int l, int r)
{
    int num = pw[r - l + 1] ;
    return max(mx[l][num], mx[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]), all_mx = max(all_mx, a[i]) ;
    if(n <= 5e3 && m <= 5e3)
    {
        for(int i = 1 ; i <= m ; i++)
        {
            int sum = 0 ;
            cin >> l[i] >> r[i] >> k[i] ;
            pair<int, int> b[n + 1] ;
            int pref[n + 1] = {} ;
            for(int i = 1 ; i <= n ; i++)
                b[i] = {a[i], i} ;
            for(int j = l[i] ; j <= r[i] ; j++)
                pref[j] = max(pref[j - 1], a[j]) ;
            sort(b + l[i], b + r[i] + 1) ;
            for(int j = l[i] ; j <= r[i] ; j++)
                if(pref[b[j].se - 1] > b[j].fi)sum = max(sum, pref[b[j].se - 1] + b[j].fi) ;
            if(sum <= k[i])
                cout << "1\n" ;
            else
                cout << "0\n" ;
        }
        return 0 ;
    }
    if(all_mx <= 1000)
    {
        for(int i = 1 ; i <= m ; i++)
        {
            cin >> l[i] >> r[i] >> k[i] ;
            qr[r[i]].push_back(i) ;
        }
        build_sparce_table3() ;
        for(int i = 1 ; i <= n ; i++)
        {
            pos[a[i]] = i ;
            for(int j : qr[i])
            {
                bool flag = 0 ;
                for(int q = 0 ; q <= all_mx ; q++)
                    if(l[j] < pos[q] && get_max(l[j], pos[q]) > q && get_max(l[j], pos[q]) + q > k[j])
                    {
                        flag = 1 ;
                        break ;
                    }
                ans[j] = 1 ^ flag ;
            }
        }
        for(int i = 1 ; i <= m ; i++)
            cout << ans[i] << '\n' ;
        return 0 ;
    }
    build_sparce_table1() ;
    for(int i = 1 ; i <= N ; i++)
    {
        int l1 = i, r1 = N + 1 ;
        while(l1 + 1 < r1)
        {
            int mid = (l1 + r1) >> 1 ;
            if(get_min1(i, mid) < a[i])r1 = mid ;
            else l1 = mid ;
        }
        ind[i] = r1 ;
    }
    build_sparce_table2() ;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> l[i] >> r[i] >> k[i] ;
        if(l[i] == r[i] || get_min2(l[i], r[i] - 1) > r[i])cout << "1\n" ;
        else cout << "0\n" ;
    }
    return 0 ;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24948 KB Output is correct
2 Correct 13 ms 24916 KB Output is correct
3 Correct 15 ms 24916 KB Output is correct
4 Correct 14 ms 24896 KB Output is correct
5 Correct 14 ms 24916 KB Output is correct
6 Correct 17 ms 25008 KB Output is correct
7 Correct 17 ms 24916 KB Output is correct
8 Correct 17 ms 25008 KB Output is correct
9 Correct 15 ms 24976 KB Output is correct
10 Correct 18 ms 25004 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24948 KB Output is correct
2 Correct 13 ms 24916 KB Output is correct
3 Correct 15 ms 24916 KB Output is correct
4 Correct 14 ms 24896 KB Output is correct
5 Correct 14 ms 24916 KB Output is correct
6 Correct 17 ms 25008 KB Output is correct
7 Correct 17 ms 24916 KB Output is correct
8 Correct 17 ms 25008 KB Output is correct
9 Correct 15 ms 24976 KB Output is correct
10 Correct 18 ms 25004 KB Output is correct
11 Correct 77 ms 25096 KB Output is correct
12 Correct 227 ms 25176 KB Output is correct
13 Correct 267 ms 25192 KB Output is correct
14 Correct 440 ms 25372 KB Output is correct
15 Correct 453 ms 25208 KB Output is correct
16 Correct 507 ms 25312 KB Output is correct
17 Correct 558 ms 25288 KB Output is correct
18 Correct 605 ms 25156 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 223344 KB Output is correct
2 Correct 864 ms 223272 KB Output is correct
3 Correct 854 ms 223408 KB Output is correct
4 Correct 877 ms 223248 KB Output is correct
5 Correct 934 ms 223352 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24948 KB Output is correct
2 Correct 13 ms 24916 KB Output is correct
3 Correct 15 ms 24916 KB Output is correct
4 Correct 14 ms 24896 KB Output is correct
5 Correct 14 ms 24916 KB Output is correct
6 Correct 17 ms 25008 KB Output is correct
7 Correct 17 ms 24916 KB Output is correct
8 Correct 17 ms 25008 KB Output is correct
9 Correct 15 ms 24976 KB Output is correct
10 Correct 18 ms 25004 KB Output is correct
11 Correct 77 ms 25096 KB Output is correct
12 Correct 227 ms 25176 KB Output is correct
13 Correct 267 ms 25192 KB Output is correct
14 Correct 440 ms 25372 KB Output is correct
15 Correct 453 ms 25208 KB Output is correct
16 Correct 507 ms 25312 KB Output is correct
17 Correct 558 ms 25288 KB Output is correct
18 Correct 605 ms 25156 KB Output is correct
19 Incorrect 459 ms 215564 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24948 KB Output is correct
2 Correct 13 ms 24916 KB Output is correct
3 Correct 15 ms 24916 KB Output is correct
4 Correct 14 ms 24896 KB Output is correct
5 Correct 14 ms 24916 KB Output is correct
6 Correct 17 ms 25008 KB Output is correct
7 Correct 17 ms 24916 KB Output is correct
8 Correct 17 ms 25008 KB Output is correct
9 Correct 15 ms 24976 KB Output is correct
10 Correct 18 ms 25004 KB Output is correct
11 Correct 77 ms 25096 KB Output is correct
12 Correct 227 ms 25176 KB Output is correct
13 Correct 267 ms 25192 KB Output is correct
14 Correct 440 ms 25372 KB Output is correct
15 Correct 453 ms 25208 KB Output is correct
16 Correct 507 ms 25312 KB Output is correct
17 Correct 558 ms 25288 KB Output is correct
18 Correct 605 ms 25156 KB Output is correct
19 Correct 849 ms 223344 KB Output is correct
20 Correct 864 ms 223272 KB Output is correct
21 Correct 854 ms 223408 KB Output is correct
22 Correct 877 ms 223248 KB Output is correct
23 Correct 934 ms 223352 KB Output is correct
24 Incorrect 453 ms 114724 KB Output isn't correct
25 Halted 0 ms 0 KB -