Submission #340725

#	Time	Username	Problem	Language	Result	Execution time	Memory
340725		NachoLibre	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	210 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];
			}
		}
		sp = max(sp, max(l->sp, r->sp));
		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;
	int dl, dr, dm;
	for(int i = 0; i < v.size(); ++i) {
		mxg = max(mxg, v[i]->sp);
		if(i && v[i]->v[0] < am) {
			dl = 0, dr = (int)v[i]->v.size() - 1;
			while(dl < dr) {
				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]);
	}
	#ifdef WEEE
	// cout << "[]! " << mxg << endl;
	#endif
	return (k >= mxg);
}

mt19937 rnd(time(0));

int R(int l, int r) {
	int d = rnd();
	return l + d % (r - l + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s = "LA'MAO";
	while(true) {
		s += s;
	}
	n = m = 1000000;
	for(int i = 1; i <= n; ++i) {
		a[i] = R(0, 1000000000);
	}
	bid(1, n, rt);
	for(int mi = 1; mi <= m; ++mi) {
		int l, r, k;
		l = R(1, n);
		r = R(l, n);
		k = R(0, 1000000000);
		// cout << qvw(l, r, k) << "\n";
		#ifdef WEEE
		// cout << flush;
		#endif
	}
	cout << "[]!" << endl;
	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:17:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while(ld < l->v.size() || rd < r->v.size()) {
      |         ~~~^~~~~~~~~~~~~
sortbooks.cpp:17:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   while(ld < l->v.size() || rd < r->v.size()) {
      |                             ~~~^~~~~~~~~~~~~
sortbooks.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    if(ld == l->v.size()) {
      |       ~~~^~~~~~~~~~~~~~
sortbooks.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    } else if(rd == r->v.size()) {
      |              ~~~^~~~~~~~~~~~~~
sortbooks.cpp: In function 'bool qvw(int, int, int)':
sortbooks.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vwv*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 0; i < v.size(); ++i) {
      |                 ~~^~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:111:10: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  111 |   int l, r, k;
      |          ^
sortbooks.cpp:111:13: warning: variable 'k' set but not used [-Wunused-but-set-variable]
  111 |   int l, r, k;
      |             ^

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