Submission #475423

#	Time	Username	Problem	Language	Result	Execution time	Memory
475423		ismoilov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1203 ms	63600 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int maxx = 1e6+6;

int tr[maxx];
int n;
vector <int> ad[maxx];

void add(int id, int val){
	while(id > 0){
		tr[id] = max(tr[id], val);
		id -= id & -id;
	}
}

int get(int id){
	int s = 0;
	while(id <= n){
		s = max(s, tr[id]);
		id += id & -id;
	}
	return s;
}

void S()
{
	int m;
	cin >> n >> m;
	vector <int> a(n+1), b(n+1), c(n+1), k(n+1);
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	
	vector <int> st;
	
	for(int i = 1; i <= m; i ++){
		cin >> b[i] >> c[i] >> k[i];
		ad[c[i]].push_back(i);
	}
	
	vector <bool> ans(m+1);
	
	for(int i = 1; i <= n; i ++){
		
		while(st.size() > 0 && a[i] >= a[st.back()])
			st.pop_back();
		
		int x = (st.size() == 0 ? 0 : st.back());
		add(x, a[x] + a[i]);

		for(int it : ad[i])
			ans[it] = (get(b[it]) <= k[it]);
		st.push_back(i);
	}

	for(int i = 1; i <= m; i++)
		cout << ans[i] << "\n";
}

int main()
{
	IOS;
	/*int t;
	cin >> t;
	while(t --)*/
		S();
}

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