Submission #344403

#	Time	Username	Problem	Language	Result	Execution time	Memory
344403		Tosic	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	244 ms	44908 KiB

sortbooks

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

int n, m, a[maxn], allR[maxn], ans;

vector<int> sorted[maxn];

void init(int idx, int l, int r){
	if(l == r){
		sorted[idx]={a[l]};
		return;
	}
	int mid = (r+l)/2, lC = idx*2+1, rC = idx*2+2;
	init(lC, l, mid);
	init(rC, mid+1, r);
	sorted[idx].resize(sorted[lC].size()+sorted[rC].size());
	int tmp = lower_bound(sorted[rC].begin(), sorted[rC].end(), sorted[lC].back()) - sorted[rC].begin();
	--tmp;
	allR[idx] = max(allR[lC], allR[rC]);
	if(!sorted[lC].empty() and !sorted[rC].empty() and tmp >= 0){
		allR[idx] = max(allR[idx], sorted[rC][tmp] + sorted[lC].back() );
	}
	merge(sorted[lC].begin(), sorted[lC].end(), sorted[rC].begin(), sorted[rC].end(), sorted[idx].begin());
	//sort(sorted[idx].begin(), sorted[idx].end());
}

vector<int> allIx;

int query(int idx, int l, int r, int ql, int qr){
	if(l >= ql and r <= qr){
		allIx.push_back(idx);
		return allR[idx];
	}
	if(l > qr or r<ql){
		return 0;
	}
	int mid = (l+r)/2;
	return max(query(idx*2+1, l, mid, ql, qr),query(idx*2+2, mid+1, r, ql, qr));
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	init(0, 0, n-1);
	for(int i = 0; i < m; ++i){
		int l,r,k;
		cin>>l>>r>>k;
		--l, --r;
		allIx.clear();
		int tmp = query(0,0, n-1,l,r), pr = -1;
		for(int i1 = 0; i1 < allIx.size();++i1){
			int j = allIx[i1];
			int tmpIdx=lower_bound(sorted[j].begin(), sorted[j].end(),pr)-sorted[j].begin();
			--tmpIdx;
			if(tmpIdx >= 0){
				tmp = max(sorted[j][tmpIdx] + pr, tmp);
			}
			pr = max(pr, sorted[j].back());
		}
		cout << (tmp<=k) << '\n';
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i1 = 0; i1 < allIx.size();++i1){
      |                   ~~~^~~~~~~~~~~~~~

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