Submission #1126468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126468		peacebringer1667	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2404 ms	247908 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e6 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

struct query{
	int l = 0,r = 0,k = 0;
};

int a[maxn];
query Q[maxn];

void input(int n,int q){
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	for (int i = 1 ; i <= q ; i++) cin >> Q[i].l >> Q[i].r >> Q[i].k;
}

namespace subtask1{
	bool subtask1(int n,int q){
		return max(n,q) <= 500;
	}
	
	int answer_query(int l,int r,int k,int n){
		for (int i = l ; i <= r ; i++)
		   for (int j = l ; j < i ; j++)
		     if (a[j] > a[i] && a[i] + a[j] > k) return 0;
		return 1;
	}
	
	void solve(int n,int q){
		for (int i = 1 ; i <= q ; i++)
			cout << answer_query(Q[i].l,Q[i].r,Q[i].k,n) << "\n";
	}
}

namespace subtask2{
	bool subtask2(int n,int q){
		return max(n,q) <= 5000;
	}
	
	int answer_query(int l,int r,int k,int n){
		int M = 0;
		for (int i = l ; i <= r ; i++){
			if (M > a[i] && a[i] + M > k) return 0;
			maxi(M,a[i]);
		}
		
		return 1;
	}
	
	void solve(int n,int q){
		for (int i = 1 ; i <= q ; i++)
			cout << answer_query(Q[i].l,Q[i].r,Q[i].k,n) << "\n";
	}
}

namespace subfull{
	const int inf = 1e9 + 1e7;
	
	vector <int> lst[4*maxn],node;
	int seg[4*maxn];
	
	/////////
	int getdif(int x,int id){
		if (!lst[id].size() || x <= lst[id][0]) return 0;
		
		int l = 0,r = lst[id].size() - 1,vt = 0;
		while (l <= r){
			int w = (l + r)/2;
			if (lst[id][w] < x){
				vt = w;
				l = w + 1;
			}
			else r = w - 1;
		}
		
		return x + lst[id][vt];
	}	
	void prepare_lst(int l,int r,int v){
		for (int i = l ; i <= r ; i++)
		    lst[v].push_back(a[i]);	
		sort(lst[v].begin(),lst[v].end());
		
		if (l == r) return;
		int w = (l + r)/2;
		
		prepare_lst(l,w,2*v + 1);
		prepare_lst(w + 1,r,2*v + 2);
		
		seg[v] = max(seg[2*v + 1],seg[2*v + 2]);
		maxi(seg[v],getdif(lst[2*v + 1].back(),2*v + 2));	
	}
	/////////
	
	void prepare(int n){
		prepare_lst(1,n,0);
	}
	
	void gen_list(int l,int r,int v,int lx,int rx){
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx){
			node.push_back(v);
			return;
		}
		
		int w = (l + r)/2;
		gen_list(l,w,2*v + 1,lx,rx);
		gen_list(w + 1,r,2*v + 2,lx,rx);
	}
	
	int answer_query(int l,int r,int k,int n){
		node.clear();
		gen_list(1,n,0,l,r);
		
		int M = 0;
		for (int u : node){
			if (seg[u] > k || getdif(M,u) > k) return 0;
			
			maxi(M,lst[u].back());
		}
		
		return 1;
	}
	
	void solve(int n,int q){
		prepare(n);
		
		for (int i = 1 ; i <= q ; i++)
		  cout << answer_query(Q[i].l,Q[i].r,Q[i].k,n) << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
//    freopen("STONE.inp","r",stdin);
//    freopen("STONE.out","w",stdout);
    
    int n,q;
    cin >> n >> q;
    input(n,q);
    
    if (subtask1::subtask1(n,q)){
    	subtask1::solve(n,q);
    	return 0;
	}
	
	if (subtask2::subtask2(n,q)){
		subtask2::solve(n,q);
		return 0;
	}
	
	subfull::solve(n,q);

	return 0;
}

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