Submission #1280490

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

const int N = 1e6+10, Q = 1e6+10;
const int inf = 1e9+10;

const int logN = 20, maxN = (1<<logN), stpos = maxN - 1;
pii T1[(maxN<<1)];
int T2[(maxN<<1)];

int n, q;
int val[N];
pii sortedval[N];
set < int > s;
vector < int > v;
pair < pii, int > queries[Q];
int rastavljeni[2 * logN][Q];
int rastavljeni_size[Q];
pair < pii, pii > cur_rastavljeni_val[Q];
queue < int > qu[N];
int saz[N];
int maxsaz;
int Tsazeti[(maxN<<1)];
unordered_map < int, int > sazimanje;
int T2predicted[(maxN<<1)];

void merge1( int i ) {
	
	T1[i].F = max(T1[i*2 + 1].F, T1[i*2 + 2].F);
	T1[i].S = max(T1[i*2 + 1].S, T1[i*2 + 2].S);
	if(T2predicted[i] != 0) T1[i].S = max(T1[i].S, T1[i*2 + 1].F + T2predicted[i]);
	
}

void updateclean1( int i, int v ) {
	
	i += stpos;
	T1[i] = mp(v, 0);
	Tsazeti[i] = sazimanje[T1[i].F];
	T2predicted[i] = 0;
	
	while(i != 0) {
		i = (i - 1) / 2;
		T1[i].F = max(T1[i*2 + 1].F, T1[i*2 + 2].F);
		T1[i].S = 0;
		Tsazeti[i] = max(Tsazeti[i*2 + 1], Tsazeti[i*2 + 2]);
		T2predicted[i] = 0;
	}
	
	return;
}

void reload1( int i ) {
	
	i += stpos;
	
	while(i != 0) {
		i = (i - 1) / 2;
//		cout <<"K" << i << "   " << T1[i].S << "\n";
		merge1(i);
	}
	
}

void merge2( int i ) {
	
	T2[i] = max(T2[i*2 + 1], T2[i*2 + 2]);
	
}

void update2( int i, int v ) {
	
	i += stpos;
	T2[i] = v;
	
	while(i) {
		i = (i - 1) / 2;
		merge2(i);
	}
	
}

void buildT1() {
	
	s.clear();
	v.clear();
	
	int cur, sazpos = 0;
	
	for(int i = 0; i < n; i++) update2(i, -inf);
	
	for(int i = 0; i < n; i++) updateclean1(i, val[i]);
	
	int curmaxnode = stpos + n - 1, curminnode = stpos;
	
	while(curminnode != 0) {
		curmaxnode = (curmaxnode - 1) / 2;
		curminnode = (curminnode - 1) / 2;
		for(int i = curminnode; i <= curmaxnode; i++) {
			qu[Tsazeti[i*2 + 1]].push(i);
		}
	}
	
	for(int i = 0; i < maxsaz; i++) {
		while(!qu[i].empty()) {
			cur = qu[i].front();
//			cout << "XX" << i << " " << cur << "    ";
			qu[i].pop();
			T2predicted[cur] = T2[cur * 2 + 2];
//			cout << T2predicted[cur] << "\n";
		}
		
		while(sazpos != n && saz[sortedval[sazpos].S] <= i) {
			update2(sortedval[sazpos].S, sortedval[sazpos].F);
			sazpos++;
		}
	}
	
	for(int i = 0; i < n; i++) reload1(i);
	
}

void rastavi_query( int i, int l, int r, int lo, int hi, int query_index) {
	
	if(l >= hi || r <= lo) return;
	
	if(l >= lo && r <= hi) {
		rastavljeni[rastavljeni_size[query_index]][query_index] = i;
		rastavljeni_size[query_index]++;
		return;
	}
	
	rastavi_query(i*2 + 1, l, l + (r-l) / 2, lo, hi, query_index);
	rastavi_query(i*2 + 2, l + (r-l) / 2, r, lo, hi, query_index);
	
}

void task() {
	
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> val[i];
		sortedval[i].F = val[i];
		sortedval[i].S = i;
	}
	
	sort(sortedval, sortedval + n);
	
	for(int i = 1; i < n; i++) {
//		cout << sortedval[i].F << " " << sortedval[i - 1].F << "\n";
		saz[sortedval[i].S] = saz[sortedval[i - 1].S] + 1;
		if(sortedval[i].F == sortedval[i - 1].F) saz[sortedval[i].S]--;
		sazimanje[sortedval[i].F] = saz[sortedval[i].S];
	}
	
	maxsaz = saz[sortedval[n - 1].S] + 1;
	
	for(int i = 0; i < q; i++) {
		cin >> queries[i].F.F >> queries[i].F.S >> queries[i].S;
		rastavi_query(0, 0, maxN, --queries[i].F.F, queries[i].F.S, i);
	}
	
//	for(int i = 0; i < q; i++) {
//		cout << i << ":\n";
//		for(int j = 0; j < (int) rastavljeni[i].size(); j++) {
//			cout << rastavljeni[i][j] << " ";
//		}
//		cout << "\n";
//	}
	
	buildT1();
	
	for(int i = 0; i < n; i++) update2(i, -inf);
	
	for(int i = 0; i < q; i++) {
		if(rastavljeni_size[i] != 0) {
			cur_rastavljeni_val[i] = mp(T1[rastavljeni[0][i]], mp(1, Tsazeti[rastavljeni[0][i]]));
			if((int) rastavljeni_size[i] != cur_rastavljeni_val[i].S.F) qu[cur_rastavljeni_val[i].S.S].push(i);
		}
	}
	
	int sazpos = 0, cur;
	pair < pii, pii > temp;
	int curTnode;
	
	for(int i = 0; i < maxsaz; i++) {
		while(!qu[i].empty()) {
//			cout << "X " << i << "\n";
			cur = qu[i].front();
//			cout << cur << ":\n";
//			cout << cur_rastavljeni_val[cur].F.F << " " << cur_rastavljeni_val[cur].F.S << " " << cur_rastavljeni_val[cur].S.F << " " << cur_rastavljeni_val[cur].S.S << "\n";
			curTnode = rastavljeni[cur_rastavljeni_val[cur].S.F][cur];
			qu[i].pop();
//			cout << cur_rastavljeni_val[cur].F.F << " " << cur_rastavljeni_val[cur].F.S << " " << cur_rastavljeni_val[cur].S.F << " " << cur_rastavljeni_val[cur].S.S << "\n";
			
			temp.F.F = max(cur_rastavljeni_val[cur].F.F, T1[curTnode].F);
			temp.F.S = max(cur_rastavljeni_val[cur].F.S, T1[curTnode].S);
			temp.F.S = max(temp.F.S, cur_rastavljeni_val[cur].F.F + T2[curTnode]);
			temp.S.F = cur_rastavljeni_val[cur].S.F + 1;
			temp.S.S = max(cur_rastavljeni_val[cur].S.S, Tsazeti[curTnode]);
			
			cur_rastavljeni_val[cur] = temp;
			
			if((int) rastavljeni_size[cur] > cur_rastavljeni_val[cur].S.F) qu[cur_rastavljeni_val[cur].S.S].push(cur);
			
//			cout << i << "\n";
//			cout << "\n";
		}
		
		while(sazpos != n && saz[sortedval[sazpos].S] <= i) {
			update2(sortedval[sazpos].S, sortedval[sazpos].F);
			sazpos++;
//			cout << i << "\n";
		}
	}
	
//	cout << n << "\n";
	
//	for(int i = 0; i < n; i++) cout << Tsazeti[i + stpos] << " ";
//	cout << "\n";
	
	for(int i = 0; i < n; i++) updateclean1(i, 0);
	
	for(int i = 0; i < q; i++) cout << (cur_rastavljeni_val[i].F.S <= queries[i].S) << "\n";
	
}

int main( void ) {
	
	FIO;
	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