Blue Bridge Cup group 2021a - two way sorting

analysis

Want to get full marks , We must not adopt conventional ideas , The problem needs to be simplified , Otherwise, the time limit will be exceeded
Simplification ：

1. The first time must be “0”, Otherwise, it doesn't make sense
2. Two consecutive identical operations , Choose a wide range of
3. It can be seen from the above that , Operation must be “0101” Alternate , If the current operation is larger than the previous same operation , Then the previous two operations will be invalid ,eg：“101”->“0”

Thus, the partial boundary can be determined according to each operation , In ascending order, the left end is determined , In descending order, the right end is determined , Finally, determine the middle part according to the number of operations .

Code

#include <iostream>

using namespace std;

const int N = 100010;
pair<int, int> stk[N]; 
int ans[N];

int main() { 
    
	int n, m;
	int p, q;
	int top = 0;//stk Top pointer of stack  
	cin >> n >> m;
	
	// Compression adjustment times  
	while (m--) { 
    
		cin >> p >> q;
		if (p == 0) { 
    
			if (top && stk[top].first == 0) { 
     
				// Simplified twice is 0 The situation of  
				//00
				q = max(q, stk[top--].second);
			} 
			while (top >= 2 && stk[top-1].second <= q) { 
    
				// If the current operation is larger than the previous same operation , Then the previous two operations will be invalid 
				//010 
				top -= 2;
			} 
			stk[++top] = { 
    0, q}; // Save operation  
		}
		else if (top) { 
    
			if (top && stk[top].first == 1) { 
     
				// Simplified twice is 0 The situation of  
				//11
				q = min(q, stk[top--].second);
			}
			while (top >= 2 && stk[top-1].second >= q) { 
    
				// If the current operation is larger than the previous same operation , Then the previous two operations will be invalid 
				//010 
				top -= 2;
			} 
			stk[++top] = { 
    1, q}; // Save operation 
		}
	}
	
	int left = 1, right = n, k = n;
	for (int i = 1; i <= top; i++) { 
    
		// Determine both ends  
		if (stk[i].first == 0) { 
    
			while (right > stk[i].second && left <= right) { 
    
				ans[right--] = k--;
			}
		}
		else { 
    
			while (left < stk[i].second && left <= right) { 
    
				ans[left++] = k--; 
			}
		}
		if (left > right) { 
    
			break;
		} 
	} 
	
	// Deal with the intermediate  
	if (top % 2) { 
    
		// The last sort is ascending  
		while (left <= right) { 
    
			ans[left++] = k--;
		}
	}
	else { 
    
		// The last sort is descending  
		while (left <= right) { 
    
			ans[right--] = k--; 
		}
	}
	
	for (int i = 1; i <= n; i++) { 
    
		cout << ans[i] << " ";
	}

	return 0;
}

reference ：https://www.bilibili.com/video/BV1pY41187dZ?spm_id_from=333.1007.top_right_bar_window_view_later.content.click