Submission #1280569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280569		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3104 ms	249060 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;
int T[(maxN<<1)];
queue < int > qu;

int n, q;
int vals[N];
int sols[Q];
int k[N];
int order[Q];
pii remaining[Q];
pii sortedvals[N];
int sazeto[N];
pii par[logN][N];

set < int > s;

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

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

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

void taskquery( int i, 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;
		}
	}
	
	remaining[i] = mp(l, r);
	
	sols[i] = out;
}

bool cussort( int a, int b ) {
	return (vals[remaining[a].F] < vals[remaining[b].F]);
}

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);
	}
	
	int cur = 0;
	for(int i = 0; i < n; i++) {
		while(sortedvals[i].F > sortedvals[cur].F) {
			update(sortedvals[cur].S, sortedvals[cur].F);
			cur++;
		}
		
		par[0][sortedvals[i].S].S = query(0, 0, maxN, sortedvals[i].S + 1, par[0][sortedvals[i].S].F);
		if(par[0][sortedvals[i].S].S != 0) par[0][sortedvals[i].S].S += sortedvals[i].F;
	}
	
	for(int i = 0; i < n; 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;
	
	for(int i = 0; i < q; i++) {
		cin >> l >> r >> k[i];
		taskquery(i, --l, r);
	}
	
	for(int i = 0; i < n; i++) update(i, 0);
	
	cur = 0;
	int temp;
	
	for(int i = 0; i < q; i++) order[i] = i;
	sort(order, order + q, cussort);
	for(int i = 0; i < q; i++) {
		while(vals[remaining[order[i]].F] > sortedvals[cur].F) {
			update(sortedvals[cur].S, sortedvals[cur].F);
			cur++;
		}
		
		temp = query(0, 0, maxN, remaining[order[i]].F, remaining[order[i]].S);
		if(temp != 0) temp += vals[remaining[order[i]].F];
		sols[order[i]] = max(sols[order[i]], temp);
	}
	
	for(int i = 0; i < q; i++) cout << (sols[i] <= k[i]) << "\n";
	
	for(int i = 0; i < n; i++) update(i, 0);
	
}

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

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