#include "wall.h" #include <iostream> #include <algorithm> #include <vector> using namespace std; //Maintain a set of updates, update it at left and right points of every update //Sort the updates by index //Segtree over update indices // // void q(int i) // { // cout << i << '\n'; // } struct segtree { int l; int r; int mn; int mx; segtree* left; segtree* right; segtree(); segtree(int L, int R); void enable(int i, int op, int height); void disable(int i); int rangemin(int L, int R); int rangemax(int L, int R); void printmax(); void printmin(); }; vector<int> enable[2000000]; vector<int> disable[2000000]; segtree::segtree() { ; } segtree::segtree(int L, int R) { l = L; r = R; if(l == r) return; int m = (l+r+2)/2 - 1; //for -1 left = new segtree(l, m); right = new segtree(m+1, r); } void segtree::enable(int i, int op, int height) { if(i < l || r < i) return; if(op == 1) { if(l == r) mx = height; else { left->enable(i, 1, height); right->enable(i, 1, height); mx = max(left->mx, right->mx); } } else { if(l == r) mn = height; else { left->enable(i, 2, height); right->enable(i, 2, height); mn = min(left->mn, right->mn); } } } void segtree::disable(int i) { if(i < l || r < i) return; if(l == r) { mn = 1e5+1; mx = 0; } else { left->disable(i); right->disable(i); mx = max(left->mx, right->mx); mn = min(left->mn, right->mn); } } int segtree::rangemin(int L, int R) { if(R < l || r < L) return 1e5+1; if(L <= l && r <= R) { return mn; } return min(left->rangemin(L, R), right->rangemin(L, R)); } int segtree::rangemax(int L, int R) { if(R < l || r < L) return 0; if(L <= l && r <= R) return mx; return max(left->rangemax(L, R), right->rangemax(L, R)); } void segtree::printmax() { if(left == NULL) cout << mx << ' '; else { left->printmax(); right->printmax(); } } void segtree::printmin() { if(left == NULL) cout << mn << ' '; else { left->printmin(); right->printmin(); } } segtree* T; int N; int K; int binary_search_res(int a, int b) { // cout << "search " << a << ' ' << b << '\n'; if(a == b) { if(T->rangemin(a, a) == 1e5+1) return T->rangemin(a+1, K-1); else return T->rangemax(a+1, K-1); } int m = (a+b)/2+1; if(a == -1 && b == 0) m = 0; // cout << m << ' ' << T->rangemin(m, N-1) << ' ' << T->rangemax(m, N-1) << '\n'; if(T->rangemin(m, K-1) <= T->rangemax(m, K-1)) return binary_search_res(m, b); else return binary_search_res(a, m-1); } //1 = max, 2 = min void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { N = n; K = k; segtree S(-1, k-1); S.enable(-1, 2, 0); T = &S; for(int j = 0; j < k; j++) { enable[left[j]].push_back(j); disable[right[j]].push_back(j); } int temp = 0; for(int i = 0; i < n; i++) { // cout << "i = " << i << '\n'; for(int j: enable[i]) { S.enable(j, op[j], height[j]); // cout << "enable " << j << '\n'; // S.printmax(); // cout << '\n'; // S.printmin(); // cout << '\n'; } if(enable[i].size() != 0 || (i > 0 && disable[i-1].size() != 0)) { temp = binary_search_res(-1, k-1); // cout << temp << '\n'; // cout << "\n\n\n"; } for(int j: disable[i]) { S.disable(j); // cout << "disable " << j << '\n'; // S.printmax(); // cout << '\n'; // S.printmin(); // cout << "\n\n\n"; } finalHeight[i] = temp; } }