제출 #223637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223637		wilwxk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1949 ms	51900 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]);
}

컴파일 시 표준 에러 (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