Submission #1094007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094007		Muhammet	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	221 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

const int N = 1e5+5;

int n, m, l[N], r[N], k[N], p[N], a[N], sp[N][30], b[N][1005];

vector <int> v[1005];

int main(){
	// ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m;
	int mx = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i-1] + (a[i] < a[i-1]);
		sp[i][0] = a[i];
		mx = max(mx,a[i]);
		v[a[i]].push_back(i);
	}
	for(int i = 1; i <= n; i++){
		if(i == v[a[i]].back()){
			for(int j = i; j <= n; j++){
				b[j][a[i]] = i;
			}
			continue;
		}
		int t = *upper_bound(v[a[i]].begin(), v[a[i]].end(), i);
		for(int j = i; j < t; j++){
			b[j][a[i]] = i;
		}
	}
	for(int j = 1; j <= 25; j++){
		for(int i = 1; i <= n-(1<<j)+1; i++){
			sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i = 1; i <= m; i++){
		cin >> l[i] >> r[i] >> k[i];
		int k1 = 0;
		for(int j = 0; j <= mx; j++){
			// cout << j << ' ';
			// cout << t << '\n';
			int ind = b[r[i]][j];
			if(ind-1 < l[i]) continue;
			// cout << l[i] << ' ' << ind << '\n';
			ind--;
			int lg = log2(ind-l[i]+1);
			// cout << lg << '\n';
			int x = max(sp[l[i]][lg], sp[ind-(1<<lg)+1][lg]);
			if(x > j) k1 = max(k1, x-j);
		}
		cout << (k1 <= k[i]) << '\n';
	}
}

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