This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
#ifdef _WIN32
constexpr int N = 1e2;
#else
constexpr int N = 1e6;
#endif
struct segtree
{
ll size = 1, val[N] = {0};
p64 ops[N];
const p64 neutral = p32(INT_MIN,INT_MAX);
segtree(int n){ while(size<n) size*=2;fill(ops,ops+N,neutral);}
void merge(p64& a, p64& b){
a.fi = min(max(a.fi,b.fi),b.se);
a.se = min(a.se,b.se);
}
void propagate(int x, int s){
if(s==1){
val[x] = max(val[x],ops[x].fi);
val[x] = min(val[x],ops[x].se);
}
else{
merge(ops[2*x+1],ops[x]);
merge(ops[2*x+2],ops[x]);
}
ops[x] = neutral;
}
void set(int l, int r, p64 u){
set(l,r,u,0,0,size);
}
void set(int l, int r,p64 u, int x, int lx, int rx){
propagate(x,rx-lx);
if(rx<=l||lx>=r) return;
else if(rx<=r&&lx>=l){
merge(ops[x],u);
return;
}
int m = (rx+lx)/2;
set(l,r,u,2*x+1,lx,m);
set(l,r,u,2*x+2,m,rx);
propagate(2*x+1,m-lx);
propagate(2*x+2,m-lx);
}
int get(int i){
return get(i,0,0,size);
}
int get(int i, int x, int lx, int rx){
propagate(x,rx-lx);
if(rx-lx==1) return val[x];
int m = (rx+lx)/2;
propagate(2*x+1,m-lx);
propagate(2*x+2,m-lx);
if(i<m) return get(i,2*x+1,lx,m);
else return get(i,2*x+2,m,rx);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree sgt(n);
for (size_t i = 0; i < k; i++)
{
p64 o; if(op[i]==1) o = p64((ll)height[i],(ll)INT_MAX);
else o = p64((ll)INT_MIN,(ll)height[i]);
sgt.set(left[i],right[i]+1,o);
}
for (size_t i = 0; i < n ; i++)
{
finalHeight[i] = sgt.get(i);
}
}
#ifdef _WIN32
signed main()
{
int n;
int k;
int i, j;
int status = 0;
freopen("sample-2.in", "r", stdin);
freopen("input.out", "w", stdout);
cin>>n>>k;
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
#endif
Compilation message (stderr)
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:88:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | for (size_t i = 0; i < k; i++)
| ~~^~~
wall.cpp:94:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | for (size_t i = 0; i < n ; i++)
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |