Submission #1280561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280561		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	148 ms	327680 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;

struct Tnode {
	
	int l, r;
	int v;
	pii chi;
	
	Tnode( void ) {
		chi = mp(-1, -1);
		l = -1;
		r = -1;
		v = 0;
	}
	
};

const int N = 1e6+10, Q = 1e6+10;
const int logN = 20, maxN = (1<<logN);
int curTnode;
Tnode T[(maxN<<1) + ((logN + 1) * Q)];
vector < int > roots;

int n, q;
int vals[N];
pii sortedvals[N];
int sazeto[N];
pii par[logN][N];

set < int > s;

void buildT( int i, int l, int r ) {
	
	curTnode++;
	T[i].l = l;
	T[i].r = r;
	
	if(r - l > 1) {
		T[i].chi.F = curTnode;
		buildT(curTnode, l, l + (r-l)/2);
		
		T[i].chi.S = curTnode;
		buildT(curTnode, l + (r-l)/2, r);
	}
	
}

void update( int i, int iold, int x, int v ) {
	
	curTnode++;
	T[i].l = T[iold].l;
	T[i].r = T[iold].r;
	
	if(T[i].r - T[i].l == 1) {
		T[i].v = v;
		return;
	}
	
	int mid = T[i].l + (T[i].r - T[i].l)/2;
	
	if(x < mid) {
		T[i].chi.F = curTnode;
		T[i].chi.S = T[iold].chi.S;
		update(curTnode, T[iold].chi.F, x, v);
		T[i].v = max(T[T[i].chi.F].v, T[T[i].chi.S].v);
		return;
	}
	
	T[i].chi.F = T[iold].chi.F;
	T[i].chi.S = curTnode;
	update(curTnode, T[iold].chi.S, x, v);
	T[i].v = max(T[T[i].chi.F].v, T[T[i].chi.S].v);
	
}

int query( int i, int lo, int hi ) {
	
	if(T[i].l >= hi || T[i].r <= lo) return 0;
	
	if(T[i].l >= lo && T[i].r <= hi) return T[i].v;
	
	return max(query(T[i].chi.F, lo, hi), query(T[i].chi.S, lo, hi));
}

void oneupdate( int i, int v ) {
	
	roots.pb(curTnode);
	update(curTnode, roots[(int) roots.size() - 2], i, v);
	
}

int taskquery( int l, int r ) {
	
	int out = 0;
	
	for(int i = logN - 1; i >= 0; i--) {
		if(par[i][l].F < r) {
			out = max(out, par[i][l].S);
			l = par[i][l].F;
		}
	}
	
	int temp = query(roots[sazeto[l]], l + 1, r);
	if(temp) temp += vals[l];
	
	out = max(out, temp);
	
	return out;
}

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);
	
	for(int i = 0; i < n; i++) {
		sazeto[sortedvals[i].S] = i;
		if(i != 0 && sortedvals[i - 1].F == sortedvals[i].F) sazeto[sortedvals[i].S] = sazeto[sortedvals[i - 1].S];
		oneupdate(sortedvals[i].S, sortedvals[i].F);
	}
	
	s.insert(n);
	for(int i = n - 1; i >= 0; i--) {
		par[0][sortedvals[i].S].F = *s.lower_bound(sortedvals[i].S);
		s.insert(sortedvals[i].S);
	}
	
	for(int i = 0; i < n; i++) {
		par[0][i].S = query(roots[sazeto[i]], i + 1, par[0][i].F);
		if(par[0][i].S != 0) par[0][i].S += vals[i];
	}
	
	par[0][n] = mp(n, 0);
	
	for(int i = 0; i < logN - 1; i++) {
		for(int j = 0; j < n + 1; j++) {
			par[i + 1][j].F = par[i][par[i][j].F].F;
			par[i + 1][j].S = max(par[i][j].S, par[i][par[i][j].F].S);
		}
	}
	
	int l, r, k;
	
	for(int i = 0; i < q; i++) {
		cin >> l >> r >> k;
		cout << (taskquery(--l, r) <= k) << "\n";
	}
	
}

int main( void ) {
	
	FIO;
	
	roots.pb(0);
	buildT(0, 0, maxN);
	
	int tt = 1;
	while(tt--) task();
	
	return 0;
}

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