oj.uz

Submission #781427

# Submission time Handle Problem Language Result Execution time Memory
781427 2023-07-13T06:11:34 Z ZHIRDILBILDIZ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 2633 ms 188716 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
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 <= 5e2 && m <= 5e2)
//    {
//        while(m--)
//        {
//            int l, r, k, b[n + 1], sum = 0 ;
//            cin >> l >> r >> k ;
//            for(int i = 1 ; i <= n ; i++)
//                b[i] = a[i] ;
//            for(int i = l ; i <= r ; i++)
//            {
//                int mn = 1e9 + 1, ind ;
//                for(int j = i ; j <= r ; j++)
//                    if(mn > b[j])
//                    {
//                        mn = b[j] ;
//                        ind = j ;
//                    }
//                for(int q = ind ; q > i ; q--)
//                {
//                    sum = max(sum, b[q] + b[q - 1]) ;
//                    swap(b[q], b[q - 1]) ;
//                }
//            }
//            if(sum <= k)
//                cout << "1\n" ;
//            else
//                cout << "0\n" ;
//        }
//        return 0 ;
//    }
    if(n <= 5e3 && m <= 5e3)
    {
        while(m--)
        {
            int l, r, k, sum = 0 ;
            cin >> l >> r >> k ;
            pair<int, int> b[n + 1] ;
            int pref[n + 1] = {} ;
            for(int i = 1 ; i <= n ; i++)
                b[i] = {a[i], i} ;
            for(int i = l ; i <= r ; i++)
                pref[i] = max(pref[i - 1], a[i]) ;
            sort(b + l, b + r + 1) ;
            for(int i = l ; i <= r ; i++)
                if(pref[b[i].se - 1] > b[i].fi)sum = max(sum, pref[b[i].se - 1] + b[i].fi) ;
            if(sum <= k)
                cout << "1\n" ;
            else
                cout << "0\n" ;
        }
        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 ;
}
//10 100
//5 6 1 3 5 7 1 2 1 0
//3 6 0

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 5 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 5 ms 212 KB Output is correct
11 Correct 69 ms 320 KB Output is correct
12 Correct 220 ms 476 KB Output is correct
13 Correct 257 ms 420 KB Output is correct
14 Correct 444 ms 528 KB Output is correct
15 Correct 440 ms 524 KB Output is correct
16 Correct 497 ms 480 KB Output is correct
17 Correct 538 ms 456 KB Output is correct
18 Correct 577 ms 448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2489 ms 186776 KB Output is correct
2 Correct 2633 ms 186720 KB Output is correct
3 Correct 2492 ms 186660 KB Output is correct
4 Correct 2555 ms 186660 KB Output is correct
5 Correct 2541 ms 186720 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 181416 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 5 ms 212 KB Output is correct
11 Correct 69 ms 320 KB Output is correct
12 Correct 220 ms 476 KB Output is correct
13 Correct 257 ms 420 KB Output is correct
14 Correct 444 ms 528 KB Output is correct
15 Correct 440 ms 524 KB Output is correct
16 Correct 497 ms 480 KB Output is correct
17 Correct 538 ms 456 KB Output is correct
18 Correct 577 ms 448 KB Output is correct
19 Incorrect 753 ms 188716 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 212 KB Output is correct
7 Correct 5 ms 212 KB Output is correct
8 Correct 5 ms 212 KB Output is correct
9 Correct 3 ms 212 KB Output is correct
10 Correct 5 ms 212 KB Output is correct
11 Correct 69 ms 320 KB Output is correct
12 Correct 220 ms 476 KB Output is correct
13 Correct 257 ms 420 KB Output is correct
14 Correct 444 ms 528 KB Output is correct
15 Correct 440 ms 524 KB Output is correct
16 Correct 497 ms 480 KB Output is correct
17 Correct 538 ms 456 KB Output is correct
18 Correct 577 ms 448 KB Output is correct
19 Correct 2489 ms 186776 KB Output is correct
20 Correct 2633 ms 186720 KB Output is correct
21 Correct 2492 ms 186660 KB Output is correct
22 Correct 2555 ms 186660 KB Output is correct
23 Correct 2541 ms 186720 KB Output is correct
24 Incorrect 527 ms 181416 KB Output isn't correct
25 Halted 0 ms 0 KB -