Submission #599254

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
599254	2022-07-19T12:05:11 Z	M_W	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	966 ms	19416 KB

sortbooks

    #include <bits/stdc++.h>
    #define ii pair<int, int>
    using namespace std;
    int t[1000001 << 2];
    bool t2[1000001 << 2];
    int a[1000001];
    bool aa[1000001];

    void build(int v, int l, int r){
        if(l == r){
            t[v] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(v * 2, l, mid); build(v * 2 + 1, mid + 1, r);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
    
    void build2(int v, int l, int r){
        if(l == r){
            t2[v] = aa[l];
            return;
        }
        int mid = (l + r) >> 1;
        build2(v * 2, l, mid); build2(v * 2 + 1, mid + 1, r);
        t2[v] = t2[v * 2] & t2[v * 2 + 1];
    }

    int query(int v, int tl, int tr, int l, int r){
        if(l > r) return -1;
        if(tl == l && tr == r) return t[v];
        int tm = (tl + tr) >> 1;
        return max(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }

    int query2(int v, int tl, int tr, int l, int r){
        if(l > r) return true;
        if(tl == l && tr == r) return t2[v];
        int tm = (tl + tr) >> 1;
        return query2(v * 2, tl, tm, l, min(r, tm)) & query2(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
    }
     
    int main(){
        int N, M;
        scanf("%d %d", &N, &M);
        for(int i = 1; i <= N; i++){
            scanf("%d", &a[i]);
            if(a[i] >= a[i - 1]) aa[i - 1] = true;
        }

        build(1, 1, N); build2(1, 1, N - 1);
        while(M--){
            int n, b, k;
            scanf("%d %d %d", &n, &b, &k);
            // int l = n, r = b;

            // printf("!>> %d %d\n", n, b);
            // while(l < r){
            //     int mid = (l + r) >> 1;
            //     int ll = query(1, 1, N, n, mid), rr = query(1, 1, N, mid + 1, b);
            //     if(ll <= rr) l = mid + 1;
            //     else r = mid;
            // }
            // int ll = query(1, 1, N, n, l), rr = query(1, 1, N, l + 1, b);
            // printf(">> %d %d\n", ll, rr);
            // if(l == r && rr != -1 && ll + rr > k) printf("0\n");
            // else printf("1\n");
            bool res = query2(1, 1, N - 1, n, b - 1);
            if(res) printf("1\n");
            else printf("0\n");
        }
    }

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", &a[i]);
      |             ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf("%d %d %d", &n, &b, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	867 ms	19416 KB	Output is correct
2	Correct	861 ms	17832 KB	Output is correct
3	Correct	836 ms	17780 KB	Output is correct
4	Correct	966 ms	17864 KB	Output is correct
5	Correct	851 ms	17856 KB	Output is correct