Submission #1280552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280552		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3103 ms	220864 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;
pair < pii, int > queries[Q];
int rastavljeni_size[Q];
pair < pii, pii > cur_rastavljeni_val[Q];
vector< int > qu[N];
int saz[N];
int maxsaz;
int Tsazeti[(maxN<<1)];
unordered_map < int, int > sazimanje;
int T2predicted[(maxN<<1)];
pii Tlr[(maxN<<1)];
int curpos[Q];
pair < bool, bool > lrchi[Q];

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();
	
	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_back(i);
		}
	}
	
	for(int i = 0; i < maxsaz; i++) {
		while(!qu[i].empty()) {
			cur = qu[i].back();
//			cout << "XX" << i << " " << cur << "    ";
			qu[i].pop_back();
			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 next_step( int i ) {
	
//	cout << i << "\n";
	
	if(lrchi[i] == mp((bool) 1, (bool) 1) || (Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)
	 || Tlr[curpos[i]].F >= queries[i].F.S || Tlr[curpos[i]].S <= queries[i].F.F) {
		if(curpos[i]&1) lrchi[i] = mp(1, 0);
		else lrchi[i] = mp(1, 1);
		curpos[i] = (curpos[i] - 1) / 2;
		return;
	}
	
	
	if(!lrchi[i].F) {
		lrchi[i] = mp(0, 0);
		curpos[i] = curpos[i] * 2 + 1;
		return;
	}
	
	lrchi[i] = mp(0, 0);
	curpos[i] = curpos[i] * 2 + 2;
	
}

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;
		queries[i].F.F--;
	}
	
//	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++) {
		curpos[i] = 0;
		lrchi[i] = mp(0, 0);
		while((lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) && !(Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)) next_step(i);
		cur_rastavljeni_val[i] = mp(T1[curpos[i]], mp(1, Tsazeti[curpos[i]]));
		next_step(i);
		while((lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) && !(Tlr[curpos[i]].F >= queries[i].F.F && Tlr[curpos[i]].S <= queries[i].F.S)) next_step(i);
		if(lrchi[i] != mp((bool) 1, (bool) 1) || curpos[i] != 0) qu[cur_rastavljeni_val[i].S.S].push_back(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].back();
//			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 = curpos[cur];
			qu[i].pop_back();
//			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;
			
			next_step(cur);
			
			while((lrchi[cur] != mp((bool) 1, (bool) 1) || curpos[cur] != 0) && !(Tlr[curpos[cur]].F >= queries[cur].F.F && Tlr[curpos[cur]].S <= queries[cur].F.S)) next_step(cur);
			
			if(lrchi[cur] != mp((bool) 1, (bool) 1) || curpos[cur] != 0) qu[cur_rastavljeni_val[cur].S.S].push_back(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";
	
	curpos[10] = 0;
	queries[10] = mp(mp(0, 3), 1);
	lrchi[10] = mp(0, 0);
	
}

int main( void ) {
	
	FIO;
	for(int i = 0; i < maxN; i++) Tlr[i + stpos] = mp(i, i + 1);
	for(int i = stpos - 1; i >= 0; i--) {
		Tlr[i].F = Tlr[i*2+1].F;
		Tlr[i].S = Tlr[i*2+2].S;
	}
	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