Submission #1280630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280630		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	60 / 100	2526 ms	88568 KiB

sortbooks

#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pii pair < int, int >
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;

using namespace std;

const int N = 1e6+10, Q = 1e6+10;
const int logN = 20, maxN = (1<<logN), stpos = maxN - 1;
int curTnode;
pair < pii, int > T[(maxN<<1)];

int n, q;
set < int > s;
int par[N];
int vals[N];
pii sortedvals[N];

pair < pii, int > mergeformula( pair < pii, int > a, pair < pii, int > b ) {
	
	pair < pii, int > out;
	if(a.F >= b.F) {
		out.F = a.F;
		if(b.F.F != 0 && b.F.F != a.F.F) out.S = max(a.S, a.F.F + b.F.F);
		else out.S = a.S;
	}
	
	else {
		out.F = b.F;
		out.S = max(a.S, b.S);
		if(a.F.S != 0) out.S = max(out.S, a.F.F + a.F.S);
	}
	
	return out;
}

void merge( int i ) {
	
	T[i] = mergeformula(T[i*2+1], T[i*2+2]);
	
}

void update( int i, pair < pii, int > v ) {
	
	i += stpos;
	T[i] = v;
	
	while(i) {
		i = (i - 1) / 2;
		merge(i);
	}
	
}

pair < pii, int > query( int i, int l, int r, int lo, int hi ) {
	
	if(l >= hi || r <= lo) return mp(mp(0, 0), 0);
	
	if(l >= lo && r <= hi) return T[i];
	
	return mergeformula(query(i*2 + 1, l, l + (r-l)/2, lo, hi),
	                    query(i*2 + 2, l + (r-l)/2, r, lo, hi));
}

void task() {
	
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> vals[i];
		sortedvals[i] = mp(vals[i], i);
	}
	
	sort(sortedvals, sortedvals + n);
	
	s.clear();
	s.insert(n);
	for(int i = n - 1; i >= 0; i--) {
		par[sortedvals[i].S] = *s.lower_bound(sortedvals[i].S);
		s.insert(sortedvals[i].S);
	}
	
	for(int i = 0; i < n; i++) {
		update(i, mp(mp(vals[i], 0), 0));
	}
	
	pair < pii, int > temp;
	for(int i = 0; i < n; i++) {
		temp = query(0, 0, maxN, i + 1, par[i]);
		update(i, mp(mp(vals[i], temp.F.F), 0));
	}
	
	int l, r, k;
	
	for(int i = 0; i < q; i++) {
		cin >> l >> r >> k;
		cout << (query(0, 0, maxN, --l, r).S <= k) << "\n";
	}
	
	
}

int main( void ) {
	
	FIO;
	
	int tt = 1;
	while(tt--) task();
	
	return 0;
}

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