Submission #223636

#	Time	Username	Problem	Language	Result	Execution time	Memory
223636		wilwxk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1915 ms	51760 KiB

sortbooks

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

const int MAXN = 1e6+5;
int book[MAXN];
int seg[MAXN*4];
int ans[MAXN];
vector<pair<int, int> > seg_ind;
vector<tuple<int, int, int, int> > qv;
int n, q;

void update(int u, int l, int r, int qi, int val) {
	if(qi < l || qi > r) return;
	if(l == r) {
		seg[u] = val;
		return;
	}
	int m = (l+r)/2;
	int vl = u*2;
	int vr = vl|1;
	update(vl, l, m, qi, val);
	update(vr, m+1, r, qi, val);
	seg[u] = max(seg[vl], seg[vr]);
}

int query(int u, int l, int r, int ql, int qr) {
	if(ql > r || qr < l) return 0;
	if(ql <= l && qr >= r) return seg[u];
	int m = (l+r)/2;
	int vl = u*2;
	int vr = vl|1;
	return max( query(vl, l, m, ql, qr), query(vr, m+1, r, ql, qr) );
}


int main() {
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &book[i]);
	for(int i = 1; i <= q; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		qv.push_back({a, b, c, i});
	}
	sort(qv.rbegin(), qv.rend());

	stack<int> st;
	st.push(0);
	book[0] = 2e9+9;
	for(int i = 1; i <= n; i++) {
		while(book[st.top()] <= book[i]) st.pop();
		seg_ind.push_back({st.top(), i});
		// printf("+(%d, %d)\n", i, st.top());
		st.push(i);
	}
	sort(seg_ind.rbegin(), seg_ind.rend());

	int p = 0;
	for(int i = 0; i <= q; i++) {
		int ql, qr, x, id;
		tie(ql, qr, x, id) = qv[i];
		while(p < n && seg_ind[p].first >= ql) {
			int val = book[seg_ind[p].first] + book[seg_ind[p].second];
			// printf("act %d %d %d\n", seg_ind[p].first, seg_ind[p].second, val);
			update(1, 1, n, seg_ind[p].second, val);
			p++;
		}

		int mx = query(1, 1, n, ql, qr);
		// printf(">> %d %d %d\n", ql, qr, mx);
		ans[id] = (mx <= x);
	}

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

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:38:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", &book[i]);
                              ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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