| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 994508 |
2024-06-07T18:09:18 Z |
Alfraganus |
Wall (IOI14_wall) |
C++17 |
|
3000 ms |
18088 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(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[i]);
else
finalHeight[j] = min(finalHeight[j], height[i]);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
13 ms |
632 KB |
Output is correct |
| 5 |
Correct |
14 ms |
644 KB |
Output is correct |
| 6 |
Correct |
14 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
107 ms |
8068 KB |
Output is correct |
| 3 |
Correct |
974 ms |
6232 KB |
Output is correct |
| 4 |
Execution timed out |
3039 ms |
18004 KB |
Time limit exceeded |
| 5 |
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 |
Correct |
1 ms |
496 KB |
Output is correct |
| 4 |
Correct |
14 ms |
604 KB |
Output is correct |
| 5 |
Correct |
14 ms |
636 KB |
Output is correct |
| 6 |
Correct |
14 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
79 ms |
13908 KB |
Output is correct |
| 9 |
Correct |
979 ms |
7516 KB |
Output is correct |
| 10 |
Execution timed out |
3068 ms |
18004 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
17 ms |
636 KB |
Output is correct |
| 5 |
Correct |
14 ms |
604 KB |
Output is correct |
| 6 |
Correct |
14 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
84 ms |
13872 KB |
Output is correct |
| 9 |
Correct |
968 ms |
7648 KB |
Output is correct |
| 10 |
Execution timed out |
3021 ms |
18088 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
