Submission #361390

#	Time	Username	Problem	Language	Result	Execution time	Memory
361390		pure_mem	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1131 ms	93992 KiB

sortbooks

#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e6 + 3;

int n, q, w[N], ans[N], fw[N];
vector< pair< pair<int, int>, int > > aybar[N];

void upd(int v, int val){
	for(;v <= n;v |= v + 1)
		fw[v] = max(fw[v], val);
}
int get(int v){
	int val = 0;
	for(;v >= 0;v = (v & (v + 1)) - 1)
		val = max(val, fw[v]);
	return val;
}

int main () {
	scanf("%d %d", &n, &q);
	for(int i = 1;i <= n;i++)
		scanf("%d", w + i);
	for(int i = 1, l, r, x;i <= q;i++){
		scanf("%d %d %d", &l, &r, &x);
		aybar[l].push_back(MP(MP(r, x), i));	
	}                       
	stack<int> b;
	for(int i = n;i >= 1;i--){
		while(!b.empty() && w[i] > w[b.top()])
			upd(b.top(), w[b.top()] + w[i]), b.pop();	
		b.push(i);
		for(pair< pair<int, int>, int > tmp: aybar[i])
			ans[tmp.Y] = get(tmp.X.X) <= tmp.X.Y;//, cerr << get(n - tmp.X.X + 1) << " " << tmp.Y << "\n";
	}
	for(int i = 1;i <= q;i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d", w + i);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%d %d %d", &l, &r, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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