Submission #433059

#	Time	Username	Problem	Language	Result	Execution time	Memory
433059		bigg	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2090 ms	113064 KiB

sortbooks

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

#define esq(x) x << 1 
#define dir(x) (x<<1) | 1
#define mid(x,y,t) ((x+y)>>1) + t

typedef long long ll;
const int MAXN = 1e6 + 10;
ll seg[4*MAXN];

struct inter
{
	int l, id;
	ll k;
};

std::vector<inter> queries[MAXN];

void update(int node, int x, int y, int id, ll v){
	if(x > id || y < id) return;
	if(x == y){
		seg[node] = max(seg[node], v);
		return;
	}
	update(esq(node), x, mid(x,y,0), id, v);
	update(dir(node), mid(x,y,1), y, id, v);
	seg[node] = max(seg[esq(node)], seg[dir(node)]);
}

ll query(int node, int x, int y, int l, int r){
	if(x > r || y < l) return 0;
	if(x >= l && y <= r) return seg[node];
	ll e = query(esq(node), x, mid(x,y,0), l, r);
	ll d = query(dir(node), mid(x,y,1), y, l, r);
	return max (e,d);
	
}
ll b[MAXN];
int ans[MAXN];
int n, m;
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
	for(int i = 1; i <= m; i++){
		int l, r;
		ll k;
		scanf("%d %d %lld", &l, &r, &k);
		queries[r].push_back({l,i,k});
	}
	vector<int> stac;
	for(int i = 1; i <= n; i++){
		while(!stac.empty() && b[stac.back()] <= b[i]) stac.pop_back();
		if(!stac.empty()) update(1, 1, n, stac.back(), b[stac.back()] + b[i]);
		for(int j = 0; j < queries[i].size(); j++){
			inter aqui = queries[i][j];
			ans[aqui.id] = (query(1,1,n, aqui.l, i) <= aqui.k);
		}
		stac.push_back(i);
	}
	for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<inter>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0; j < queries[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:44:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d %d %lld", &l, &r, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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