Submission #885209

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885209	2023-12-09T09:04:26 Z	damirka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	2499 ms	54800 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000010],st[1000010];    
int tree[4000040],tree1[4000040];
void build_tree(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_tree(v * 2, tl, tm);
        build_tree(v * 2 + 1, tm + 1, tr);
        tree[v] = min(tree[v * 2], tree[v * 2 + 1]);   
    }
}
void build_tree1(int v, int tl, int tr) {
    if (tl == tr) {
        tree1[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_tree1(v * 2, tl, tm);
        build_tree1(v * 2 + 1, tm + 1, tr);
        tree1[v] = max(tree1[v * 2], tree1[v * 2 + 1]);   
    }
}
int get_min(int l, int r, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    if (tr < l || r < tl) {
        return INT_MAX;     
    }
    int tm = (tl + tr) / 2;
    return min(get_min(l, r, v * 2,     tl,     tm),    
               get_min(l, r, v * 2 + 1, tm + 1, tr));
}
int get_max(int l, int r, int v, int tl, int tr) {
    if (l <= tl && tr <= r) {
        return tree1[v];
    }
    if (tr < l || r < tl) {
        return 0;     
    }
    int tm = (tl + tr) / 2;
    return max(get_max(l, r, v * 2,     tl,     tm),    
               get_max(l, r, v * 2 + 1, tm + 1, tr));
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	build_tree(1, 1, n);  
	build_tree1(1, 1, n); 
	st[1]=0;
	for(int i=1;i<n;i++){
		if(a[i+1]>=a[i]){
			st[i+1]=st[i]+1;
		}
		else{
			st[i+1]=0;
		}
	}
	for(int i=0;i<m;i++){
		int l,r,k;
		cin >> l >> r >> k;
		if(l==r){
			cout << 1 << endl;
			continue;
		}
		if(r-st[r]<=l){
			cout << 1 << endl;
			continue;
		}
		if(get_min(l,r,1,1,n)+get_max(l,r-st[r],1,1,n)<=k){
			cout << 1 << endl;
		}
		else{
			cout << 0 << endl;
		}
	}  
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6608 KB	Output is correct
3	Incorrect	2 ms	6628 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	1 ms	6608 KB	Output is correct
3	Incorrect	2 ms	6628 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2499 ms	54056 KB	Output is correct
2	Correct	2449 ms	54444 KB	Output is correct
3	Correct	2444 ms	54800 KB	Output is correct
4	Correct	2419 ms	54560 KB	Output is correct
5	Correct	1477 ms	54720 KB	Output is correct