| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 410665 | Haruto810198 | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include <algorithm>
using namespace std;
#define int long long
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
const int INF = 2147483647;
const int MAX = 2000010;
struct Node{
int sl, sr;
int tagl, tagr;
};
Node st[4*MAX];
void build(int cidx, int cl, int cr){
V.sl = cl;
V.sr = cr;
V.tagl = 0;
V.tagr = 0;
if(cl < cr){
int mid = (cl + cr) / 2;
build(cidx*2, cl, mid);
build(cidx*2+1, mid+1, cr);
}
}
void addtag(int cidx, int mmin, int mmax){
if(mmin > V.tagr){
V.tagl = V.tagr = mmin;
}
else if(mmax < V.tagl){
V.tagl = V.tagr = mmax;
}
else{
V.tagl = max(V.tagl, mmin);
V.tagr = min(V.tagr, mmax);
}
}
void pushtag(int cidx){
if(V.sl < V.sr){
addtag(cidx*2, V.tagl, V.tagr);
addtag(cidx*2+1, V.tagl, V.tagr);
}
V.tagl = -INF;
V.tagr = INF;
}
void modify(int cidx, int ml, int mr, int mmin, int mmax){
if(mr<V.sl or V.sr<ml){
return;
}
else if(ml<=V.sl and V.sr<=mr){
addtag(cidx, mmin, mmax);
return;
}
else{
pushtag(cidx);
modify(cidx*2, ml, mr, mmin, mmax);
modify(cidx*2+1, ml, mr, mmin, mmax);
}
}
int query(int cidx, int qidx){
if(V.sl==qidx and V.sr==qidx){
return V.tagl;
}
else{
pushtag(cidx);
int mid = (V.sl + V.sr) / 2;
if(qidx <= mid){
return query(cidx*2, qidx);
}
else{
return query(cidx*2+1, qidx);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 0, n-1);
FOR(i,0,k-1,1){
if(op[i]==1){ /// Max
modify(1, left[i], right[i], height[i], INF);
}
else if(op[i]==2){ /// min
modify(1, left[i], right[i], -INF, height[i]);
}
}
FOR(i,0,n-1,1){
finalHeight[i] = query(1, i);
}
}