| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 765469 | emad234 | 벽 (IOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 8e6 + 1;
ll seg[mxN],lazyMx[mxN],lazyMn[mxN];
ll N,s,e,val;
void spread(ll l,ll r, ll ind){
if(l != r){
seg[ind * 2] = max(seg[ind * 2],lazyMx[ind]);
seg[ind * 2] = min(seg[ind * 2],lazyMn[ind]);
lazyMx[ind * 2] = max(lazyMx[ind * 2],lazyMx[ind]);
lazyMn[ind * 2] = min(lazyMn[ind * 2],lazyMn[ind]);
seg[ind * 2 + 1] = max(seg[ind * 2 + 1],lazyMx[ind]);
seg[ind * 2 + 1] = min(seg[ind * 2 + 1],lazyMn[ind]);
lazyMx[ind * 2 + 1] = max(lazyMx[ind * 2 + 1],lazyMx[ind]);
lazyMn[ind * 2 + 1] = min(lazyMn[ind * 2 + 1],lazyMn[ind]);
}
lazyMn[ind] = 1e18;
lazyMx[ind] = 0;
}
void updateMn(ll l = 1,ll r = N,ll ind = 1){
if(l > e || r < s) return;
if(l >= s && r <= e){
spread(l,r,ind);
lazyMn[ind] = min(lazyMn[ind],val);
seg[ind] = min(seg[ind],val);
spread(l,r,ind);
return;
}
ll md = (l + r) / 2;
updateMn(l,md,ind * 2);updateMn(md + 1,r,ind * 2 + 1);
spread(l,r,ind);
}
void updateMx(ll l = 1,ll r = N,ll ind = 1){
if(l > e || r < s) return;
if(l >= s && r <= e){
// spread(l,r,ind);
lazyMx[ind] = max(lazyMx[ind],val);
seg[ind] = max(seg[ind],val);
cout<<l<<' '<<r<<' '<<val<<'\n';
spread(l,r,ind);
return;
}
ll md = (l + r) / 2;
updateMx(l,md,ind * 2);updateMx(md + 1,r,ind * 2 + 1);
spread(l,r,ind);
}
ll query(ll l = 1,ll r = N,ll ind = 1){
spread(l,r,ind);
if(l > e || r < s) return 0;
if(l >= s && r <= e) { spread(l,r,ind);return seg[ind];}
ll md = (l + r) / 2;
return max(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void prllseg(){
ll p2 = 1;
for(ll i = 1;i <= N * 2 - 1;i++){
spread(1,2,i);
cout<<seg[i]<<' ';
if(p2 * 2 - 1 == i){
cout<<'\n';
p2 = p2 * 2;
}
}
}
void buildWall(ll n,ll k,ll op[],ll left[],ll right[],ll height[],ll finalHeight[]){
N = exp2(ceil(log2(n)));
for(ll i = 0; i<= N;i++){
lazyMn[i] = 1e18;
}
for(ll i = 0;i < k;i++){
s = left[i] + 1,e = right[i] + 1;
val = height[i];
if(op[i] == 1){
updateMx();
}else{
updateMn();
}
}
for(ll i = 0 ; i <n;i++){
s = e = i + 1;
finalHeight[i] = query();
}
}
// main()
// {
// ll n;
// ll k;
//
// ll i, j;
// ll status = 0;
//
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
//
// ll* op = (ll*)calloc(sizeof(ll), k);
// ll* left = (ll*)calloc(sizeof(ll), k);
// ll* right = (ll*)calloc(sizeof(ll), k);
// ll* height = (ll*)calloc(sizeof(ll), k);
// ll* finalHeight = (ll*)calloc(sizeof(ll), 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 ", finalHeight[j]);
//
// return 0;
// }