| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 669838 | TS_2392 | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "wall.h"
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)
#define eb emplace_back
#define epl emplace
#define lwb lower_bound
#define upb upper_bound
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;
template<class T1, class T2> bool minimize(T1 &a, T2 &b){
if(a > b){a = b; return true;} return false;
}
template<class T1, class T2> bool maximize(T1 &a, T2 &b){
if(a < b){a = b; return true;} return false;
}
const int N = 2e6 + 3;
int res[N];
struct Node{
int Add = 0, Remove = N;
} st[N << 2];
void propag(int id, int v1, int v2){
maximize(st[id].Add, v1);
maximize(st[id].Remove, v1);
minimize(st[id].Add, v2);
minimize(st[id].Remove, v2);
}
void update(int id, int L, int R, int type, int Lq, int Rq, int h){
if(R < Lq || Rq < L) return;
if(Lq <= L && R <= Rq){
if(type == 1){
maximize(st[id].Add, h);
maximize(st[id].Remove, h);
//cout << st[id].Add << ' ' << st[id].Remove << '\n';
}
else{
minimize(st[id].Add, h);
minimize(st[id].Remove, h);
//cout << st[id].Add << ' ' << st[id].Remove << '\n';
}
return;
}
int mid = L + R >> 1;
propag(id << 1, st[id].Add, st[id].Remove);
propag(id << 1 | 1, st[id].Add, st[id].Remove);
st[id].Add = 0; st[id].Remove = N;
update(id << 1, L, mid, type, Lq, Rq, h);
update(id << 1 | 1, mid + 1, R, type, Lq, Rq, h);
}
void Get(int id, int L, int R){
if(L == R){
res[L] = st[id].Add;
return;
}
propag(id << 1, st[id].Add, st[id].Remove);
propag(id << 1 | 1, st[id].Add, st[id].Remove);
int mid = L + R >> 1;
Get(id << 1, L, mid);
Get(id << 1 | 1, mid + 1, R);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i = 0; i < k; ++i){
update(1, 0, n - 1, op[i], left[i], right[i], height[i]);
}
Get(1, 0, n - 1);
for(int i = 0; i < n; ++i) finalHeight[i] = res[i];
}