oj.uz

Submission #781588

# Submission time Handle Problem Language Result Execution time Memory
781588 2023-07-13T08:21:04 Z ZHIRDILBILDIZ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
47 / 100
 843 ms 223436 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++)
        pw[i] = pw[i / 2] + 1, 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 24956 KB Output is correct
2 Correct 12 ms 24916 KB Output is correct
3 Correct 13 ms 24916 KB Output is correct
4 Correct 16 ms 24952 KB Output is correct
5 Correct 12 ms 24972 KB Output is correct
6 Correct 16 ms 25012 KB Output is correct
7 Correct 16 ms 24912 KB Output is correct
8 Correct 16 ms 24928 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 16 ms 24944 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24956 KB Output is correct
2 Correct 12 ms 24916 KB Output is correct
3 Correct 13 ms 24916 KB Output is correct
4 Correct 16 ms 24952 KB Output is correct
5 Correct 12 ms 24972 KB Output is correct
6 Correct 16 ms 25012 KB Output is correct
7 Correct 16 ms 24912 KB Output is correct
8 Correct 16 ms 24928 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 16 ms 24944 KB Output is correct
11 Correct 76 ms 25072 KB Output is correct
12 Correct 228 ms 25168 KB Output is correct
13 Correct 272 ms 25196 KB Output is correct
14 Correct 437 ms 25140 KB Output is correct
15 Correct 443 ms 25188 KB Output is correct
16 Correct 493 ms 25224 KB Output is correct
17 Correct 529 ms 25128 KB Output is correct
18 Correct 600 ms 25168 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 223352 KB Output is correct
2 Correct 842 ms 223352 KB Output is correct
3 Correct 839 ms 223380 KB Output is correct
4 Correct 840 ms 223436 KB Output is correct
5 Correct 843 ms 223360 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 118988 KB Output is correct
2 Correct 311 ms 119912 KB Output is correct
3 Correct 417 ms 120452 KB Output is correct
4 Correct 397 ms 120680 KB Output is correct
5 Correct 367 ms 120728 KB Output is correct
6 Correct 347 ms 119508 KB Output is correct
7 Correct 356 ms 119544 KB Output is correct
8 Correct 201 ms 120292 KB Output is correct
9 Correct 212 ms 118532 KB Output is correct
10 Correct 200 ms 120292 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24956 KB Output is correct
2 Correct 12 ms 24916 KB Output is correct
3 Correct 13 ms 24916 KB Output is correct
4 Correct 16 ms 24952 KB Output is correct
5 Correct 12 ms 24972 KB Output is correct
6 Correct 16 ms 25012 KB Output is correct
7 Correct 16 ms 24912 KB Output is correct
8 Correct 16 ms 24928 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 16 ms 24944 KB Output is correct
11 Correct 76 ms 25072 KB Output is correct
12 Correct 228 ms 25168 KB Output is correct
13 Correct 272 ms 25196 KB Output is correct
14 Correct 437 ms 25140 KB Output is correct
15 Correct 443 ms 25188 KB Output is correct
16 Correct 493 ms 25224 KB Output is correct
17 Correct 529 ms 25128 KB Output is correct
18 Correct 600 ms 25168 KB Output is correct
19 Incorrect 418 ms 209216 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 24956 KB Output is correct
2 Correct 12 ms 24916 KB Output is correct
3 Correct 13 ms 24916 KB Output is correct
4 Correct 16 ms 24952 KB Output is correct
5 Correct 12 ms 24972 KB Output is correct
6 Correct 16 ms 25012 KB Output is correct
7 Correct 16 ms 24912 KB Output is correct
8 Correct 16 ms 24928 KB Output is correct
9 Correct 14 ms 24916 KB Output is correct
10 Correct 16 ms 24944 KB Output is correct
11 Correct 76 ms 25072 KB Output is correct
12 Correct 228 ms 25168 KB Output is correct
13 Correct 272 ms 25196 KB Output is correct
14 Correct 437 ms 25140 KB Output is correct
15 Correct 443 ms 25188 KB Output is correct
16 Correct 493 ms 25224 KB Output is correct
17 Correct 529 ms 25128 KB Output is correct
18 Correct 600 ms 25168 KB Output is correct
19 Correct 833 ms 223352 KB Output is correct
20 Correct 842 ms 223352 KB Output is correct
21 Correct 839 ms 223380 KB Output is correct
22 Correct 840 ms 223436 KB Output is correct
23 Correct 843 ms 223360 KB Output is correct
24 Correct 367 ms 118988 KB Output is correct
25 Correct 311 ms 119912 KB Output is correct
26 Correct 417 ms 120452 KB Output is correct
27 Correct 397 ms 120680 KB Output is correct
28 Correct 367 ms 120728 KB Output is correct
29 Correct 347 ms 119508 KB Output is correct
30 Correct 356 ms 119544 KB Output is correct
31 Correct 201 ms 120292 KB Output is correct
32 Correct 212 ms 118532 KB Output is correct
33 Correct 200 ms 120292 KB Output is correct
34 Incorrect 418 ms 209216 KB Output isn't correct
35 Halted 0 ms 0 KB -