oj.uz

Submission #249864

# Submission time Handle Problem Language Result Execution time Memory
249864 2020-07-16T07:29:42 Z minhcool Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1713 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

int n, q, w[1000005], sparse1[1000005][20], sparse2[1000005][20], sparse3[1000005][20];

int mx1(int l, int r){
	int k = log2(r - l + 1);
	return max(sparse1[l][k], sparse1[r - (1 << k) + 1][k]);
}

int mx2(int l, int r){
	int k = log2(r - l + 1);
	return max(sparse2[l][k], sparse2[r - (1 << k) + 1][k]);
}

int mn(int l, int r){
	int k = log2(r - l + 1);
	return min(sparse3[l][k], sparse3[r - (1 << k) + 1][k]);
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		sparse1[i][0] = sparse3[i][0] = w[i];
		//cout << w[i] << "\n";
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++){
			sparse1[j][i] = max(sparse1[j][i - 1], sparse1[j + (1 << (i - 1))][i - 1]);
			//cout << i << " " << j << " " << sparse1[j][i] << "\n";
		}
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++) sparse3[j][i] = min(sparse3[j][i - 1], sparse3[j + (1 << (i - 1))][i - 1]);
	}
	for(int i = 1; i <= n; i++){
		int l = 1, r = i;
		while(l < (r - 1)){
			int mid = (l + r) >> 1;
			if(mx1(mid, i) == w[i]) r = mid;
			else l = mid;
		}
		while(mx1(l, i) > w[i]) l++;
		sparse2[i][0] = l;
	}
	for(int i = 1; i <= 20; i++){
		for(int j = 1; j <= (n - (1 << i) + 1); j++) sparse2[j][i] = max(sparse2[j][i - 1], sparse2[j + (1 << (i - 1))][i - 1]);\
	}
	while(q--){
		int l, r, k;
		cin >> l >> r >> k;
		int l1 = l, r1 = r;
		while(l1 < (r1 - 1)){
			int mid = (l1 + r1) >> 1;
			if(mx2(mid, r) > l) l1 = mid;
			else r1 = mid;
		}
		while(l1 <= r && mx2(l1, r) > l) l1++;
		l1--;
		if(l1 == l){
			cout << 1 << "\n";
			continue;
		}
		//cout << mx1(l, l1) << " " << mn(l, l1) << "\n";
		cout << (k >= (mx1(l, l1) + mn(l, l1))) << "\n";
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Runtime error 15 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Runtime error 15 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1713 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 49912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Runtime error 15 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Runtime error 15 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -