#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define print(a) for(auto x : a) cout << x << ' '; cout << endl;
struct SegTree {
int size = 1;
vector<int> mins, maxs;
SegTree (int n){
while(size < n)
size <<= 1;
mins.resize(2 * size, -1);
maxs.resize(2 * size, -1);
}
void add(int l, int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
if(maxs[x] != -1){
if(maxs[x] <= v){
if(lastmax == -1)
lastmax = maxs[x];
else
lastmax = min(lastmax, maxs[x]);
maxs[x] = -1;
}
}
if(mins[x] != -1){
if(mins[x] >= v and (lastmax == -1 or lastmax == v))
return;
lastmin = max(lastmin, mins[x]);
mins[x] = -1;
}
if(l <= lx and rx <= r){
mins[x] = max(mins[x], v);
if(maxs[x] == -1)
maxs[x] = lastmin;
else
maxs[x] = min(maxs[x], lastmin);
maxs[x] = max(maxs[x], mins[x]);
return;
}
if(r <= lx or rx <= l){
if(lastmin != -1){
mins[x] = max(mins[x], lastmin);
if(maxs[x] != -1)
maxs[x] = max(maxs[x], mins[x]);
}
if(lastmax != -1){
if(maxs[x] == -1)
maxs[x] = lastmax;
else
maxs[x] = min(maxs[x], lastmax);
mins[x] = min(mins[x], maxs[x]);
}
return;
}
int mid = (lx + rx) >> 1;
add(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
add(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
}
void add(int l, int r, int v){
add(l, r, v, 0, 0, size);
}
void remove(int l, int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
if(mins[x] != -1){
if(mins[x] >= v){
lastmin = max(lastmin, mins[x]);
mins[x] = -1;
}
}
if(maxs[x] != -1){
if(max(lastmin, maxs[x]) <= v)
return;
if(lastmax == -1)
lastmax = maxs[x];
else
lastmax = min(lastmax, maxs[x]);
maxs[x] = -1;
}
if(l <= lx and rx <= r){
if(maxs[x] == -1)
maxs[x] = v;
else
maxs[x] = min(maxs[x], v);
mins[x] = max(mins[x], lastmin);
mins[x] = min(mins[x], maxs[x]);
return;
}
if(rx <= l or r <= lx){
if(lastmax != -1){
if(maxs[x] == -1)
maxs[x] = lastmax;
else
maxs[x] = min(maxs[x], lastmax);
mins[x] = min(mins[x], maxs[x]);
}
if(lastmin != -1){
mins[x] = max(mins[x], lastmin);
if(maxs[x] != -1)
maxs[x] = max(maxs[x], mins[x]);
}
return;
}
int mid = (lx + rx) >> 1;
remove(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
remove(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
}
void remove(int l, int r, int v){
remove(l, r, v, 0, 0, size);
}
int query(int ind, int x, int l, int r){
if(l + 1 == r){
if(mins[x] == -1)
return 0;
return mins[x];
}
int mid = (l + r) >> 1;
int ans = -1;
if(ind < mid)
ans = query(ind, (x << 1) + 1, l, mid);
else
ans = query(ind, (x << 1) + 2, mid, r);
int left = max(0, mins[x]), right = (maxs[x] == -1 ? 1e9 : maxs[x]);
if(left <= ans and ans <= right)
return ans;
else if(ans < left)
return left;
return right;
}
int query(int x){
return query(x, 0, 0, size);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
// SegTree s(n);
// for(int i = 0; i < k; i ++){
// if(op[i] == 1)
// s.add(left[i], right[i] + 1, height[i]);
// else
// s.remove(left[i], right[i] + 1, height[i]);
// // for(int j = 0; j < 2 * s.size - 1; j ++)
// // cout << i << ' ' << j << ' ' << s.mins[j] << ' ' << s.maxs[j] << endl;
// }
// for(int i = 0; i < n; i ++)
// finalHeight[i] = s.query(i);
for(int i = 0; i < n; i ++)
finalHeight[i] = 0;
for(int i = 0; i < k; i ++){
for(int j = left[i]; j <= right[i]; j ++){
if(op[i] == 1)
finalHeight[j] = max(finalHeight[j], height[j]);
else
finalHeight[j] = min(finalHeight[j], height[j]);
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
86 ms |
13936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
