제출 #59893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59893		hamzqq9	Wall (IOI14_wall)	C++14	100 / 100	1436 ms	218620 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define N 2000005
struct SEG {
	
	int mn,mx;

} S[N*4];

int lazy[N*4];
int n;

SEG merge(SEG x,SEG y) {

	return {min(x.mn,y.mn),max(x.mx,y.mx)};

}

void push(int node,int bas,int son) {

	if(~lazy[node]) {

		S[node*2].mx=S[node*2].mn=S[node*2+1].mx=S[node*2+1].mn=lazy[node*2]=lazy[node*2+1]=lazy[node];

		lazy[node]=-1;

	}

}

SEG get(int node,int bas,int son,int x) {

	if(bas==x && son==x) return S[node];

	push(node,bas,son);

	if(orta>=x) return get(node*2,bas,orta,x);

	return get(node*2+1,orta+1,son,x);

}

void up(int node,int bas,int son,int l,int r,int h,int typ) {

	if(bas>r || son<l) return ;

	if(typ==1) {

		if(S[node].mn>=h) return ;

	}
	else {

		if(S[node].mx<=h) return ;

	}

	if(bas>=l && son<=r) {

		if(typ==1) {

			if(S[node].mx<=h) {

				S[node].mx=S[node].mn=h;

				lazy[node]=h;

				return ;

			}

		}
		else {

			if(S[node].mn>=h) {

				S[node].mn=S[node].mx=h;

				lazy[node]=h;

				return ;

			}

		}

	}

	if(bas==son) return ;

	push(node,bas,son);

	up(node*2,bas,orta,l,r,h,typ);
	up(node*2+1,orta+1,son,l,r,h,typ);

	S[node]=merge(S[node*2],S[node*2+1]);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	
  	memset(lazy,-1,sizeof(lazy));

  	::n=n;

  	for(int i=0;i<k;i++) {

  		up(1,0,n-1,left[i],right[i],height[i],op[i]);

  	}

  	for(int i=0;i<n;i++) {

  		finalHeight[i]=get(1,0,n-1,i).mx;

  	}

}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "wall.h"

int main()
{

	freopen("sample-2.in","r",stdin);
  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;
}

*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39