| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 246954 | Evirir | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;
bool DEBUG = 1;
const int MAXN = 2000005;
struct Node {
ll mn = 0, mx = INF;
};
class LazySegmentTree {
private:
vector<Node> v, lazy;
int size_;
void update(int s, int e, const Node &val, int k, int l, int r)
{
push(k, l, r);
if(r < s || e < l) return;
if(s <= l && r <= e){
lazy[k] = val;
push(k, l, r);
return;
}
int mid = (l+r)>>1;
update(s, e, val, 2*k, l, mid);
update(s, e, val, 2*k+1, mid+1, r);
}
Node query(int s, int e, int k, int l, int r)
{
push(k, l, r);
if(r < s || e < l) return Node{-1,INF}; //dummy value
if(s <= l && r <= e) return v[k];
int mid = (l+r)/2;
Node lc = query(s, e, 2*k, l, mid);
Node rc = query(s, e, 2*k+1, mid+1, r);
return merge(lc, rc);
}
public:
LazySegmentTree(): v(vector<Node>()), lazy(vector<Node>()){}
LazySegmentTree(int n_){
for(size_=1;size_<n_;) size_<<=1;
v.resize(4*size_, Node{0,INF});
lazy.resize(4*size_, Node{-1,INF});
}
void push(int k, int l, int r){
if(lazy[k].mn != -1 || lazy[k].mx != INF){
if(lazy[k].mn != -1){
amax(v[k].mn, lazy[k].mn);
amax(v[k].mx, lazy[k].mn);
}
else
{
amin(v[k].mn, lazy[k].mx);
amin(v[k].mx, lazy[k].mx);
}
if(l!=r){
mergelazy(lazy[k*2],lazy[k]);
mergelazy(lazy[k*2+1],lazy[k]);
}
lazy[k] = Node{-1,INF};
}
}
inline Node merge(const Node &a, const Node &b){
return Node{(a.mn != -1 ? a.mn : b.mn), (a.mx != INF ? a.mx : b.mx)};
}
inline void mergelazy(Node &a, const Node &b){
amax(a.mn, b.mn);
amax(a.mx, b.mn);
amin(a.mn, b.mx);
amin(a.mx, b.mx);
}
inline void update(int s, int e, const Node &val){
update(s, e, val, 1, 0, size_-1);
}
inline Node query(int s, int e){
return query(s, e, 1, 0, size_-1);
}
};
void buildWall(int n, int K, int op[], int L[], int R[], int H[], int ans[])
{
LazySegmentTree st(n);
for(int i=0;i<K;i++)
{
if(op[i]==1) st.update(L[i],R[i],Node{H[i],INF});
else st.update(L[i],R[i],Node{-1,H[i]});
}
forn(i,0,n) ans[i] = st.query(i,i).mn;
}
int main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
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;
}