#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
const int inf=1000000100;
const int MAXN=2000010;
int A[MAXN];
pii seg[MAXN<<2];
pii Merge(pii a, pii b){
if (a.second<b.first) return {b.first, b.first};
if (b.second<a.first) return {b.second, b.second};
return {max(a.first, b.first), min(a.second, b.second)};
}
void shift(int id){
seg[id<<1]=Merge(seg[id<<1], seg[id]);
seg[id<<1 | 1]=Merge(seg[id<<1 | 1], seg[id]);
seg[id]=seg[0];
}
void Put(int id, int tl, int tr, int l, int r, pii p){
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
seg[id]=Merge(seg[id], p);
// debugp(seg[id])
return ;
}
shift(id);
int mid=(tl+tr)>>1;
Put(id<<1, tl, mid, l, r, p);
Put(id<<1 | 1, mid, tr, l, r, p);
}
void dfs(int id, int tl, int tr){
if (tr-tl==1){
A[tl]=Merge({0, 0}, seg[id]).first;
return ;
}
shift(id);
int mid=(tl+tr)>>1;
dfs(id<<1, tl, mid);
dfs(id<<1 | 1, mid, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(seg, seg+MAXN*4, pii(0, inf));
for (int i=0; i<k; i++){
int l=left[i], r=right[i]+1, h=height[i];
if (op[i]==1) Put(1, 0, n, l, r, {h, inf});
if (op[i]==2) Put(1, 0, n, l, r, {0, h});
}
dfs(1, 0, n);
for (int i=0; i<n; i++) finalHeight[i]=A[i];
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
62956 KB |
Output is correct |
| 2 |
Correct |
43 ms |
63084 KB |
Output is correct |
| 3 |
Correct |
43 ms |
63084 KB |
Output is correct |
| 4 |
Correct |
47 ms |
63212 KB |
Output is correct |
| 5 |
Correct |
45 ms |
63212 KB |
Output is correct |
| 6 |
Correct |
45 ms |
63212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
62956 KB |
Output is correct |
| 2 |
Correct |
203 ms |
71660 KB |
Output is correct |
| 3 |
Correct |
205 ms |
67308 KB |
Output is correct |
| 4 |
Correct |
494 ms |
72556 KB |
Output is correct |
| 5 |
Correct |
345 ms |
73068 KB |
Output is correct |
| 6 |
Correct |
333 ms |
73228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
62956 KB |
Output is correct |
| 2 |
Correct |
42 ms |
63084 KB |
Output is correct |
| 3 |
Correct |
43 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
47 ms |
63212 KB |
Output is correct |
| 5 |
Correct |
46 ms |
63212 KB |
Output is correct |
| 6 |
Correct |
45 ms |
63212 KB |
Output is correct |
| 7 |
Correct |
41 ms |
63104 KB |
Output is correct |
| 8 |
Correct |
204 ms |
71688 KB |
Output is correct |
| 9 |
Correct |
201 ms |
67308 KB |
Output is correct |
| 10 |
Correct |
490 ms |
72556 KB |
Output is correct |
| 11 |
Correct |
351 ms |
73068 KB |
Output is correct |
| 12 |
Correct |
329 ms |
73212 KB |
Output is correct |
| 13 |
Correct |
40 ms |
62956 KB |
Output is correct |
| 14 |
Correct |
210 ms |
71788 KB |
Output is correct |
| 15 |
Correct |
73 ms |
64236 KB |
Output is correct |
| 16 |
Correct |
617 ms |
73068 KB |
Output is correct |
| 17 |
Correct |
344 ms |
73068 KB |
Output is correct |
| 18 |
Correct |
340 ms |
73196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
62956 KB |
Output is correct |
| 2 |
Correct |
43 ms |
63084 KB |
Output is correct |
| 3 |
Correct |
42 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
48 ms |
63232 KB |
Output is correct |
| 5 |
Correct |
45 ms |
63212 KB |
Output is correct |
| 6 |
Correct |
46 ms |
63212 KB |
Output is correct |
| 7 |
Correct |
41 ms |
62956 KB |
Output is correct |
| 8 |
Correct |
201 ms |
71916 KB |
Output is correct |
| 9 |
Correct |
208 ms |
67564 KB |
Output is correct |
| 10 |
Correct |
493 ms |
72812 KB |
Output is correct |
| 11 |
Correct |
351 ms |
73324 KB |
Output is correct |
| 12 |
Correct |
333 ms |
73452 KB |
Output is correct |
| 13 |
Correct |
43 ms |
62956 KB |
Output is correct |
| 14 |
Correct |
207 ms |
71916 KB |
Output is correct |
| 15 |
Correct |
73 ms |
64164 KB |
Output is correct |
| 16 |
Correct |
618 ms |
73068 KB |
Output is correct |
| 17 |
Correct |
343 ms |
73068 KB |
Output is correct |
| 18 |
Correct |
338 ms |
73008 KB |
Output is correct |
| 19 |
Correct |
786 ms |
97772 KB |
Output is correct |
| 20 |
Correct |
769 ms |
95212 KB |
Output is correct |
| 21 |
Correct |
787 ms |
97644 KB |
Output is correct |
| 22 |
Correct |
777 ms |
95340 KB |
Output is correct |
| 23 |
Correct |
784 ms |
95468 KB |
Output is correct |
| 24 |
Correct |
780 ms |
95340 KB |
Output is correct |
| 25 |
Correct |
785 ms |
95180 KB |
Output is correct |
| 26 |
Correct |
776 ms |
97588 KB |
Output is correct |
| 27 |
Correct |
776 ms |
97644 KB |
Output is correct |
| 28 |
Correct |
763 ms |
95212 KB |
Output is correct |
| 29 |
Correct |
775 ms |
95276 KB |
Output is correct |
| 30 |
Correct |
771 ms |
95212 KB |
Output is correct |
