제출 #340743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340743		NachoLibre	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	77 / 100	2251 ms	262152 KiB

sortbooks

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

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

	int ld, rd;
	void P() {
		for(int i = 0; i < r->v.size(); ++i) {
			if(r->v[i] < l->v[l->v.size() - 1]) {
				sp = r->v[i] + l->v[l->v.size() - 1];
			}
		}
		sp = max(sp, max(l->sp, r->sp));
		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;

pair<int, int> G(pair<int, int> a, pair<int, int> b) {
	pair<int, int> c;
	if(a.first == -2) c = b;
	else if(b.first == -2) c = a;
	else if(a.first == -1 || b.first == -1) {
		c.first = -1;
	} else {
		if(a.second <= b.first) {
			c.first = a.first;
			c.second = b.second;
		} else {
			c.first = -1;
		}
	}
	return c;
}

struct vov {
	vov *l, *r;
	pair<int, int> s;

	void P() {
		s = G(l->s, r->s);
	}
} *rtt;

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;
	}
	bid(l, (l + r) / 2, t->l);
	bid((l + r) / 2 + 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) {
		v.push_back(t);
		return;
	}
	chy(l, (l + r) / 2, t->l);
	chy((l + r) / 2 + 1, r, t->r);
}

int mxg, am, dl, dr, dm;

bool qvw(int l, int r, int k) {
	v.clear();
	sl = l, sr = r;
	chy(1, n, rt);
	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) {
			dl = 0, dr = 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[v[i]->v.size() - 1]);
	}
	return (k >= mxg);
}

void bod(int l, int r, vov *&t) {
	t = new vov();
	if(l == r) {
		t->s = {a[l], a[l]};
		return;
	}
	bod(l, (l + r) / 2, t->l);
	bod((l + r) / 2 + 1, r, t->r);
	t->P();
}

pair<int, int> sgs(int l, int r, vov *t) {
	if(l > sr || r < sl) return make_pair(-2, 0);
	if(l >= sl && r <= sr) return t->s;
	return G(sgs(l, (l + r) / 2, t->l), sgs((l + r) / 2 + 1, r, t->r));
}

bool dst(int l, int r) {
	sl = l, sr = r;
	pair<int, int> p = sgs(1, n, rtt);
	if(p.first != -1) return 1;
	return 0;
}

const int M = 1000006;
int l[M], r[M], k[M], saa[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		saa[i] = a[i];
	}
	sort(saa + 1, saa + n + 1);
	bool boo = 0;
	for(int mi = 1; mi <= m; ++mi) {
		cin >> l[mi] >> r[mi] >> k[mi];
		if(k[mi] >= saa[1] + saa[2]) boo = 1;
	}
	if(!boo) {
		bod(1, n, rtt);
		for(int mi = 1; mi <= m; ++mi) {
			cout << dst(l[mi], r[mi]) << "\n";
		}
		cout << flush;
	} else {
		bid(1, n, rt);
		for(int mi = 1; mi <= m; ++mi) {
			cout << qvw(l[mi], r[mi], k[mi]) << "\n";
		}
		cout << flush;
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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