| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 861046 | MongHwa | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define X first
#define Y second
#define INF 0x7f7f7f7f
void init(vector<pair<int, int>>& lazy, int node, int start, int end)
{
if(start == end)
lazy[node] = {0, INF};
else
{
init(lazy, node*2, start, (start+end)/2);
init(lazy, node*2+1, (start+end)/2+1, end);
lazy[node] = {0, INF};
}
}
void update_lazy(vector<pair<int, int>>& lazy, int node, int start, int end)
{
if(start != end)
{
lazy[node*2].X = max(lazy[node*2].X, lazy[node].X);
lazy[node*2].Y = max(lazy[node*2].Y, lazy[node].X);
lazy[node*2+1].X = max(lazy[node*2+1].X, lazy[node].X);
lazy[node*2+1].Y = max(lazy[node*2+1].Y, lazy[node].X);
lazy[node*2].X = min(lazy[node*2].X, lazy[node].Y);
lazy[node*2].Y = min(lazy[node*2].Y, lazy[node].Y);
lazy[node*2+1].X = min(lazy[node*2+1].X, lazy[node].Y);
lazy[node*2+1].Y = min(lazy[node*2+1].Y, lazy[node].Y);
lazy[node] = {0, INF};
}
}
void update_range(vector<pair<int, int>>& lazy, int node, int start, int end, int left, int right, int type, int val)
{
update_lazy(lazy, node, start, end);
if(right < start || left > end)
return;
if(left <= start && end <= right)
{
if(type == 1)
{
lazy[node].X = max(lazy[node].X, val);
lazy[node].Y = max(lazy[node].Y, val);
}
else if(type == 2)
{
lazy[node].X = min(lazy[node].X, val);
lazy[node].Y = min(lazy[node].Y, val);
}
update_lazy(lazy, node, start, end);
return;
}
update_range(lazy, node*2, start, (start+end)/2, left, right, type, val);
update_range(lazy, node*2+1, (start+end)/2+1, end, left, right, type, val);
}
void ans(vector<pair<int, int>>& lazy, int node, int start, int end)
{
update_lazy(lazy, node, start, end);
if(start == end)
cout << lazy[node].X << '\n';
else
{
ans(lazy, node*2, start, (start+end)/2);
ans(lazy, node*2+1, (start+end)/2+1, end);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
int h = (int)ceil(log2(n));
int tree_size = (1<<(h+1));
vector<pair<int, int>> lazy(tree_size);
init(lazy, 1, 0, n-1);
while(q--)
{
int op, l, r, h;
cin >> op >> l >> r >> h;
update_range(lazy, 1, 0, n-1, l, r, op, h);
}
ans(lazy, 1, 0, n-1);
}