oj.uz

Submission #837091

# Submission time Handle Problem Language Result Execution time Memory
837091 2023-08-24T22:15:33 Z MODDI Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 328 ms 88564 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int MXN = 1e5 + 10;
	int n;
	vector<pii> tree;
	vi arr;
	int lg[MXN+1];
		
	int table[20][MXN];
	void init(int _n, vi _arr){
		n = _n;
		tree.resize(4*n);
		arr = _arr;
		lg[1] = 0;
		for(int i = 2; i <= MXN; i++)	lg[i] = lg[i/2] + 1;	
		copy(arr.begin(), arr.end(), table[0]);
		for(int i = 1; i <= lg[n]; i++){
			for(int j = 0; j + (1 << i) <= n; j++){
				table[i][j] = max(table[i-1][j], table[i-1][j + (1 << (i-1))]);
			}
		}
	}
	int query_table(int l, int r){
		int i = lg[r-l+1];
		return max(table[i][l], table[i][r - (1 << i) +1]);
	}
	void build(int node, int l, int r){
		if(l == r)	tree[node] = mp(arr[l], l);
		else{
			int mid = (l + r) / 2;
			build(node*2, l, mid);
			build(node*2+1, mid+1, r);
			tree[node] = max(tree[node*2], tree[node*2+1]);
		}
	}
	pii query(int node, int l, int r, int L, int R){
		if(r < L || l > R)	return mp(0,0);
		if(L <= l && r <= R){
			if(query_table(L, tree[node].second-1) < tree[node].first)
				return mp(0,0);
			return mp(tree[node].first + query_table(L, tree[node].second-1), tree[node].second);
		}
		int mid = (l + r) / 2;
		pii left = query(node*2, l, mid, L, R);
		pii right = query(node*2+1, mid+1, r, L, R);
		return max(left, right);
	}
int main(){
	int n, m;
	cin>>n>>m;
	arr.resize(n);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	init(n, arr);
	build(1, 0, n-1);
	while(m--){
		int l, r, k;
		cin>>l>>r>>k;
		l--; r--;
		pii here = query(1, 0, n-1, l, r);
		if(here.first > k)	cout<<0<<"\n";
		else cout<<1<<"\n";
	}
}

Subtask #1
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 328 ms 88564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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