#include <iostream> #include "wall.h" #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 = 1e5+1; int mx = 0; segtree* left = NULL; segtree* right = NULL; 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 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, 0, height); right->enable(i, 0, height); mn = min(left->mn, right->mn); } } } void 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 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 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 printmax() // { // if(left == NULL) cout << mx << ' '; // else // { // left->printmax(); // right->printmax(); // } // } // // void printmin() // { // if(left == NULL) cout << mn << ' '; // else // { // left->printmin(); // right->printmin(); // } // } }; segtree* T; int N; 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, N-1); else return T->rangemax(a+1, N-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, N-1) <= T->rangemax(m, N-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; segtree S(-1, n-1); S.enable(-1, 2, 0); T = &S; vector<int> enable[n], disable[n]; 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'; if(enable[i].size() != 0 || disable[i].size() != 0) { for(int j: enable[i]) { S.enable(j, op[j], height[j]); // cout << "enable " << j << '\n'; // // S.printmax(); // cout << '\n'; // S.printmin(); } temp = binary_search_res(-1, N-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; } }