oj.uz

Submission #884994

# Submission time Handle Problem Language Result Execution time Memory
884994 2023-12-08T19:04:06 Z damirka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 29436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 29436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 10936 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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