Submission #964898

#	Time	Username	Problem	Language	Result	Execution time	Memory
964898		Acanikolic	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3043 ms	45068 KiB

sortbooks

#include <bits/stdc++.h>
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 1000000 + 10;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9; 	

int a[N];
vector<pair<int,int>>kveri[N];
	 		 
bool cmp(pair<pair<int,int>,int>A,pair<pair<int,int>,int>B) {
	if(A.F.S < B.F.S) return true;
	return false;
}	 

long long fenw[N];

void update(int index,int n,int val) {
	while(index <= n) {
		fenw[index] += val;
		index += index & -index;
	}
}

long long get(int index) {
	long long ret = 0;
	while(index >= 1) {
		ret += fenw[index];
		index -= index & -index;
	}
	return ret;
}

long long get(int l,int r) {
	return get(r) - get(l - 1);
}
	 		 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,q;
	cin >> n >> q;
	vector<int>a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int>prev(n + 1,-1);
	stack<int>st;
	for(int i = 1; i <= n; i++) {
		while(st.size() && a[st.top()] <= a[i]) st.pop();
		if(st.size()) prev[i] = st.top();
		st.push(i);
	}
	/*for(int i = 1; i <= q; i++) {
		int l,r,k;
		cin >> l >> r >> k;
		kveri[r].pb({l,k});
	}
	for(int i = 1; i <= n; i++) {
		if(prev[i] != -1) update(prev[i],n,a[prev[i]] + )
	}*/
	while(q--) {
		int l,r,k;
		cin >> l >> r >> k;
		bool ok = true;
		for(int i = l; i <= r; i++) {
			int prv = prev[i];
			if(prv >= l) {
				if(a[prv] + a[i] > k) ok = false;
			}
		}
		cout << ok << "\n";
	}
    return 0;
}

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