| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 995123 |
2024-06-08T13:31:04 Z |
Alfraganus |
Wall (IOI14_wall) |
C++17 |
|
83 ms |
11292 KB |
#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(lastmin <= maxs[x]){
if(lastmax == -1)
lastmax = maxs[x];
else
lastmax = min(lastmax, maxs[x]);
}
else
lastmax = lastmin;
maxs[x] = -1;
}
}
if(mins[x] != -1){
if(mins[x] >= v and lastmax == -1)
return;
if(mins[x] <= lastmax or lastmax == -1)
lastmin = max(lastmin, mins[x]);
mins[x] = -1;
}
if(l <= lx and rx <= r){
mins[x] = max(mins[x], v);
if(lastmax != -1){
if(maxs[x] == -1)
maxs[x] = lastmax;
else
maxs[x] = min(maxs[x], lastmax);
}
if(maxs[x] != -1)
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(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(mins[x] != -1){
if(mins[x] >= v){
lastmin = max(lastmin, mins[x]);
mins[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){
if(height[i] != 0)
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 ++)
// cout << s.query(i) << ' ';
// cout << endl;
}
for(int i = 0; i < n; i ++)
finalHeight[i] = s.query(i); //, cout << finalHeight[i] << endl;
// cout << "ANSWER: " << endl;
// 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[i]);
// else
// finalHeight[j] = min(finalHeight[j], height[i]);
// }
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
83 ms |
11292 KB |
Output is correct |
| 3 |
Incorrect |
54 ms |
5716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
