Submission #885016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885016	2023-12-08T19:54:06 Z	damirka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	2360 ms	29716 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=0;i<n;i++){
		cin >> a[i];
	}
	build_tree(1, 0, n - 1);  
	build_tree1(1, 0, n - 1); 
	st[0]=0;
	for(int i=0;i<n-1;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-1]<=l){
			cout << 1 << endl;
			continue;
		}
		if(get_min(l-1,r-st[r-1]-1,1,0,n-1)+get_max(l-1,r-st[r-1]-1,1,0,n-1)<=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	6492 KB	Output is correct
3	Incorrect	1 ms	6492 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	6492 KB	Output is correct
3	Incorrect	1 ms	6492 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	2350 ms	29224 KB	Output is correct
2	Correct	2343 ms	29432 KB	Output is correct
3	Correct	2360 ms	29716 KB	Output is correct
4	Correct	2360 ms	29268 KB	Output is correct
5	Correct	1442 ms	29180 KB	Output is correct