Submission #340713

#	Time	Username	Problem	Language	Result	Execution time	Memory
340713		NachoLibre	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	649 ms	262148 KiB

sortbooks

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

struct vwv {
	vwv *l, *r;
	int sp;
	vector<int> v;

	void P() {
		for(int i = 0; i < r->v.size(); ++i) {
			if(r->v[i] < l->v[(int)l->v.size() - 1]) {
				sp = r->v[i] + l->v[(int)l->v.size() - 1];
			}
		}
		int ld = 0, rd = 0;
		while(ld < l->v.size() || rd < r->v.size()) {
			if(ld == l->v.size()) {
				v.push_back(r->v[rd]);
				++rd;
			} else if(rd == r->v.size()) {
				v.push_back(l->v[ld]);
				++ld;
			} else if(l->v[ld] < r->v[rd]) {
				v.push_back(l->v[ld]);
				++ld;
			} else {
				v.push_back(r->v[rd]);
				++rd;
			}
		}
	}
} *rt;

const int N = 1000006;
int a[N];

void bid(int l, int r, vwv *&t) {
	t = new vwv();
	if(l == r) {
		t->v.push_back(a[l]);
		return;
	}
	int m = (l + r) / 2;
	bid(l, m, t->l);
	bid(m + 1, r, t->r);
	t->P();
}

int n, m;

vector<vwv*> v;

int sl, sr;
void chy(int l, int r, vwv *t) {
	if(l > sr || r < sl) return;
	if(l >= sl && r <= sr) return v.push_back(t);
	int m = (l + r) / 2;
	chy(l, m, t->l);
	chy(m + 1, r, t->r);
}

bool qvw(int l, int r, int k) {
	v.clear();
	sl = l, sr = r;
	chy(1, n, rt);
	int mxg = 0, am = 0;
	for(int i = 0; i < v.size(); ++i) {
		mxg = max(mxg, v[i]->sp);
		if(i && v[i]->v[0] < am) {
			int dl = 0, dr = (int)v[i]->v.size() - 1;
			while(dl < dr) {
				int dm = (dl + dr + 1) / 2;
				if(v[i]->v[dm] < am) {
					dl = dm;
				} else {
					dr = dm - 1;
				}
			}
			mxg = max(mxg, am + v[i]->v[dl]);
		}
		am = max(am, v[i]->v[(int)v[i]->v.size() - 1]);
	}
	// cout << "[]! " << mxg << " " << k << endl;
	return (k >= mxg);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	bid(1, n, rt);
	for(int mi = 1; mi <= m; ++mi) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << qvw(l, r, k) << (vector<string>){"\n", ""}[mi == m];
	}
	cout << flush;
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void vwv::P()':
sortbooks.cpp:10:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i = 0; i < r->v.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
sortbooks.cpp:16:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   while(ld < l->v.size() || rd < r->v.size()) {
      |         ~~~^~~~~~~~~~~~~
sortbooks.cpp:16:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   while(ld < l->v.size() || rd < r->v.size()) {
      |                             ~~~^~~~~~~~~~~~~
sortbooks.cpp:17:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    if(ld == l->v.size()) {
      |       ~~~^~~~~~~~~~~~~~
sortbooks.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |    } else if(rd == r->v.size()) {
      |              ~~~^~~~~~~~~~~~~~
sortbooks.cpp: In function 'bool qvw(int, int, int)':
sortbooks.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vwv*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < v.size(); ++i) {
      |                 ~~^~~~~~~~~~

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