Submission #334557

#	Time	Username	Problem	Language	Result	Execution time	Memory
334557		Gurban	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	901 ms	260580 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e3+5;
const int maxn=1e6+5;
int n,m,a[maxn],l,r,k,mx,ans;
int sp[22][maxn],num,last[N],answ[maxn];
vector<pair<int,pair<int,int>>>qr[maxn];

int f(int l,int r){
	assert(l<=r);
	int lg = __lg(r - l+1);
	return min(sp[lg][l],sp[lg][r-(1<<lg)+1]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		sp[0][i] = a[i];
	}

	int lg = __lg(n);
	for(int i = 1;i <= lg;i++)
		for(int j = 1;j <= n;j++) sp[i][j] = min(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
	
	for(int i = 1;i <= m;i++){
		cin >> l >> r >> k;
		qr[l].push_back({r,{k,i}});
		if(n <= 5000){
			mx = 0,ans = 0;
			for(int i = l;i <= r;i++){
				if(mx > a[i]) ans = max(ans,mx+a[i]);
				mx = max(mx,a[i]);
			}
			if(ans <= k) cout<<"1\n";
			else cout<<"0\n";
		}
	}
	if(n <= 5000) return 0;
	for(int i = n;i >= 1;i--){
		for(auto j : qr[i]){
			int jog = 0;
			for(int k = 1;k <= 1000;k++){
				num = -1;
				if(last[k] != 0 and last[k] < j.first) num = f(last[k]+1,j.first);
				if(num != -1 and num < k) jog = max(jog,k+num);
			}
			if(jog > j.second.first) answ[j.second.second]=0;
			else answ[j.second.second]=1;
		}
		last[a[i]]=i;
	}
	for(int i = 1;i <= m;i++) cout<<answ[i]<<'\n';
}

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