#include "wall.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int sz = 2e6+5;
pii segtree[4*sz];
void build(int v, int l, int r)
{
if(l == r)
segtree[v] = {0, 0};
else
{
int mid = (l + r) / 2;
build(2*v, l, mid);
build(2*v+1, mid+1, r);
segtree[v] = {0, 0};
}
}
void push1(int v, int l, int r)
{
if(l != r)
{
if(segtree[v].f >= segtree[2*v].s)
segtree[2*v] = {segtree[v].f, segtree[v].f};
else if(segtree[v].s <= segtree[2*v].f)
segtree[2*v] = {segtree[v].s, segtree[v].s};
else
segtree[2*v] = {max(segtree[v].f, segtree[2*v].f), min(segtree[v].s, segtree[2*v].s)};
if(segtree[v].f >= segtree[2*v+1].s)
segtree[2*v+1] = {segtree[v].f, segtree[v].f};
else if(segtree[v].s <= segtree[2*v+1].f)
segtree[2*v+1] = {segtree[v].s, segtree[v].s};
else
segtree[2*v+1] = {max(segtree[v].f, segtree[2*v+1].f), min(segtree[v].s, segtree[2*v+1].s)};
segtree[v] = {0, INT_MAX};
}
}
void update1(int v, int l, int r, int tl, int tr, int val)
{
push1(v, l, r);
if(l > r || l > tr || r < tl)
return;
if(tl <= l && r <= tr)
{
if(l == r){
segtree[v] = {max(val, segtree[v].f), max(val, segtree[v].f)};
return;
}
segtree[v] = {val, LLONG_MAX};
push1(v, l, r);
return;
}
int mid = (l + r) / 2;
update1(2*v, l, mid, tl, tr, val);
update1(2*v+1, mid+1, r, tl, tr, val);
}
void update2(int v, int l, int r, int tl, int tr, int val)
{
push1(v, l, r);
if(l > r || l > tr || r < tl)
return;
if(tl <= l && r <= tr)
{
if(l == r){
segtree[v] = {min(val, segtree[v].f), min(val, segtree[v].f)};
return;
}
segtree[v] = {0, val};
push1(v, l, r);
return;
}
int mid = (l + r) / 2;
update2(2*v, l, mid, tl, tr, val);
update2(2*v+1, mid+1, r, tl, tr, val);
}
pii findres(int v, int l, int r, int tl, int tr)
{
if(l > r || l > tr || r < tl)
return {0, INT_MAX};
push1(v, l, r);
if(tl <= l && r <= tr)
return segtree[v];
int mid = (l + r) / 2;
pii lans = findres(2*v, l, mid, tl, tr);
pii rans = findres(2*v+1, mid+1, r, tl, tr);
return {max(lans.f, rans.f), 0};
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 1, n);
for(int i = 0; i < k; i++)
{
if(op[i] == 1)
update1(1, 1, n, left[i]+1, right[i]+1, height[i]);
else
update2(1, 1, n, left[i]+1, right[i]+1, height[i]);
}
for(int i = 0; i < n; i++)
finalHeight[i] = findres(1, 1, n, i+1, i+1).f;
}
| # |
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 |
Incorrect |
1 ms |
348 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 |
82 ms |
8312 KB |
Output is correct |
| 3 |
Incorrect |
149 ms |
5980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 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 |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
