Submission #1190980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190980		lovrot	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	3098 ms	107192 KiB

sortbooks

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>

#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e6 + 10;

int n, w[N], l[N], k[N];

int prf[N], suf[N];
vector<pii> q[N], mxq[N];
set<int> s;

bool ans[N];

void dnc(int lo, int hi) { 
	if(lo + 1 >= hi) { return; }
	int mi = (lo + hi) / 2;

	dnc(lo, mi);
	dnc(mi, hi);

	deb("%d %d %d:\n", lo, mi, hi);

	prf[mi] = 0;
	suf[mi - 1] = 0;
	for(int i = mi - 1, mx = 0; i >= lo; --i) { 
		mx = max(mx, w[i]);
		prf[i] = prf[i + 1];

		auto it = s.lower_bound(w[i]);
		if(it != s.begin()) { prf[i] = max(prf[i], w[i] + *prev(it)); }
		s.insert(w[i]);

		for(auto it = lower_bound(q[i].begin(), q[i].end(), make_pair(mi, -1)); it != q[i].end() && it->X < hi; ++it) {
			mxq[it->X].PB({mx, it->Y});
			deb("%d %d\n", i, it->X);
		}	
	}

	s.clear();

	for(int i = mi; i < hi; ++i) { 
		suf[i] = suf[i - 1];

		if(!s.empty() && *prev(s.end()) > w[i]) { suf[i] = max(suf[i], w[i] + *prev(s.end())); }
		s.insert(w[i]);

		for(pii j : mxq[i]) { 
			int mx = max(prf[l[j.Y]], suf[i]);

			auto it = s.lower_bound(j.X);
			if(it != s.begin()) { 
				mx = max(mx, j.X + *prev(it));
			}

			deb("%d, %d %d %d\n", j.X, prf[l[j.Y]], mx, suf[i]);
			ans[j.Y] = mx > k[j.Y];
		}

		mxq[i].clear();
	}

	s.clear();
}

int main() { 
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) { scanf("%d", w + i); }
	for(int i = 0; i < m; ++i) {
		int r;
		scanf("%d%d%d", l + i, &r, k + i);

		q[l[i]].PB({r, i});
	}

	for(int i = 1; i <= n; ++i) { 
		sort(q[i].begin(), q[i].end());
		deb("%d: ", i);
		for(pii j : q[i]) deb("(%d %d) ", j.X, j.Y);
		deb("\n");
	}

	dnc(1, n + 1);

	for(int i = 0; i < m; ++i) printf("%d\n", ans[i] ^ 1); 
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:81:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         for(int i = 1; i <= n; ++i) { scanf("%d", w + i); }
      |                                       ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |                 scanf("%d%d%d", l + i, &r, k + i);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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