Submission #884994

#	Time	Username	Problem	Language	Result	Execution time	Memory
884994		damirka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3051 ms	29436 KiB

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(){
	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(get_min(l-1,r-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;
		}
	}  
    //Можно делать запросы вида get_min(l, r, 1, 0, n - 1) и update(idx, val, 1, 0, n - 1);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23