Submission #1134662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134662		hamzabc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3101 ms	132456 KiB

sortbooks

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


vector<long long int> lst, cvp;
long long int N, M;


void divq(long long int l, long long int r, vector<array<long long int, 4>> q){
	long long int m = (l + r) >> 1;
	vector<array<long long int, 4>> q1, q2, q3;
	q1.reserve(q.size());
	q2.reserve(q.size());
	q3.reserve(q.size());
	for (auto i : q){
		if (i[1] < m)
			q1.push_back(i);
		else if (i[0] > m){
			q3.push_back(i);
		}else{
			q2.push_back(i);
		}
	}
	
	if (q1.size())
		divq(l, m - 1, q1);
	q1.clear();
	if (q3.size())
		divq(m + 1, r, q3);
	q3.clear();

	sort(all(q2), [](const array<long long int, 4> &a, const array<long long int, 4> &b) -> bool{ return a[1] < b[1]; });
	
	vector<long long int> pref(m - l + 1);
	vector<long long int> cost(m - l + 1);
	pref[0] = lst[m];
	cost[0] = 0;
	for (int i = 1; i <= m - l; i++){
		if (pref[i - 1] >= lst[m - i]){
			pref[i] = pref[i - 1];
			cost[i] = cost[i - 1];
		}else{
			pref[i] = lst[m - i];
			cost[i] = lst[m - i] + pref[i - 1];
		}
	}

	set<long long int> sayilar;
	long long int mincost = 0, mxval = LONG_LONG_MIN;
	for (auto quest : q2){
		while ((long long int)sayilar.size() + m <= quest[1]){
			if (mxval < lst[sayilar.size() + m]){
				mxval = lst[sayilar.size() + m];
			}else{
				mincost = max(mincost, mxval + lst[sayilar.size() + m]);
			}
			sayilar.insert(lst[sayilar.size() + m]);
		}
		if (quest[2] < mincost || quest[2] < cost[m - quest[0]]){
			cvp[quest[3]] = false;
			continue;
		}
		if (sayilar.lower_bound(pref[m - quest[0]]) == sayilar.begin()){
			continue;
		}
		if (*prev(sayilar.lower_bound(pref[m - quest[0]])) + pref[m - quest[0]] > quest[2]){
			cvp[quest[3]] = false;
		}
	}
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	lst.resize(N);
	for (int i = 0; i < N; i++)
		cin >> lst[i];
	vector<array<long long int, 4>> q;
	q.reserve(M);
	cvp.resize(M, 1);
	for (int i = 0; i < M; i++){
		long long int a, b, w;
		cin >> a >> b >> w;
		a--; b--;
		if (a != b)
			q.push_back({a, b, w, i});
	}
	divq(0, N, q);
	for (int i = 0; i < M; i++){
		cout << cvp[i] endl;
	}
	return 0;
}

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