| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 153842 | dennisstar | 벽 (IOI14_wall) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX=(1<<21);
int ans[(1<<21)];
struct seg{
pii pi[(1<<22)];
void lazy(int val, int ind, int op) {
if (op==1) {
pi[ind].fi=max(val, pi[ind].first);
pi[ind].se=max(val, pi[ind].second);
}
if (op==2) {
pi[ind].fi=min(val, pi[ind].first);
pi[ind].se=min(val, pi[ind].second);
}
}
void update(int s, int e, int i, int ds, int de, int h, int op) {
if (!(s<=de&&ds<=e)) return ;
if (s<=ds&&de<=e) {
lazy(h, i, op);
if (s==e) ans[s]=pi[i].fi;
}
else {
lazy(pi[i].fi, i*2, 1); lazy(pi[i].se, i*2, 2);
lazy(pi[i].fi, i*2+1, 1); lazy(pi[i].se, i*2+1, 2);
pi[i]={0,(1<<30)};
int md=(ds+de)/2;
update(s, e, i*2, ds, md, h, op);
update(s, e, i*2+1, md+1, de, h, op);
}
}
}T;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0; i<k; i++) T.update(left[i], right[i], 1, 0, n-1, height[i], op[i]);
for (int i=0; i<n; i++) T.update(i, i, 1, 0, n-1, 0, 1);
for (int i=0; i<n; i++) finalHeight[i]=ans[i];
return;
}