| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 782680 | Trumling | 벽 (IOI14_wall) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
long long INF=99999999999999;
#define MOD 1000000007
#define all(x) x.begin(),x.end()
struct node
{
ll m=INF;
ll M=0;
};
ll ans[1000000];
node seg[8000000];
void lazy(int idx)
{
seg[idx*2].m=max(seg[idx].M,seg[idx*2].m);
seg[idx*2].M=max(seg[idx].M,seg[idx*2].M);
seg[idx*2].m=min(seg[idx].m,seg[idx*2].m);
seg[idx*2].M=min(seg[idx].m,seg[idx*2].M);
seg[idx*2+1].m=max(seg[idx].M,seg[idx*2+1].m);
seg[idx*2+1].M=max(seg[idx].M,seg[idx*2+1].M);
seg[idx*2+1].m=min(seg[idx].m,seg[idx*2+1].m);
seg[idx*2+1].M=min(seg[idx].m,seg[idx*2+1].M);
seg[idx]={INF,0};
return ;
}
void up(int l,int r,int idx,int op,ll u,int L,int R)
{
if(l>R || r<L)
return ;
if(L<=l && r<=R)
{
if(op==1)
{
seg[idx].m=max(seg[idx].m,u);
seg[idx].M=max(seg[idx].M,u);
}
else
{
seg[idx].m=min(seg[idx].m,u);
seg[idx].M=min(seg[idx].M,u);
}
return ;
}
lazy(idx);
up(l,(l+r)/2,idx*2,op,u,L,R);
up((l+r)/2+1,r,idx*2+1,op,u,L,R);
}
void fin(int l,int r,int idx)
{
if(l==r)
{
ans[l]=seg[idx].M;
return ;
}
lazy(idx);
fin(l,(l+r)/2,idx*2);
fin((l+r)/2+1,r,idx*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<k;i++)
up(0,n-1,1,op[i],height[i],left[i],right[i]);
fin(0,n-1,1);
for(int i=0;i<n;i++)
finalHeight[i]=ans[i];
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
int main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), 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\n", finalHeight[j]);
return 0;
}