Submission #1093984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093984		Muhammet	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3076 ms	16300 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];

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];
		v[a[i]].push_back(i);
		mx = max(mx,a[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++){
			if(sz(v[j]) == 0) continue;
			// cout << j << ' ';
			int t = (upper_bound(v[j].begin(), v[j].end(), r[i]) - v[j].begin() - 1);
			// cout << t << '\n';
			if(t == -1 or v[j][t]-1 < l[i]) continue;
			int ind = v[j][t]-1;
			// cout << l[i] << ' ' << ind << '\n';
			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