제출 #125028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125028		baluteshih	Wall (IOI14_wall)	C++14	100 / 100	710 ms	83832 KiB

wall

#include "wall.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define MP make_pair
#define pii pair<int,int> 
#define pll pair<long long,long long>
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;

struct node
{
	int U,D;
}seg[6000004];

const int INF = 100000;

inline void add(int a,int x)
{
	if(!~seg[a].U) seg[a].D=max(seg[a].D,x);
	else
		if(x>=seg[a].U) seg[a].U=-1,seg[a].D=x;
		else seg[a].D=max(seg[a].D,x);
}

inline void remove(int a,int x)
{
	if(!~seg[a].U) seg[a].D=min(seg[a].D,x);
	else 
		if(x<=seg[a].D) seg[a].U=-1,seg[a].D=x;
		else seg[a].U=min(seg[a].U,x);
}

inline void down(int l,int r,int rt)
{
	if(l==r) return;
	if(!~seg[rt].U) 
		seg[rt<<1].U=-1,seg[rt<<1].D=seg[rt].D,seg[rt<<1|1].U=-1,seg[rt<<1|1].D=seg[rt].D;
	else 
	{
		if(seg[rt].D!=0) add(rt<<1,seg[rt].D),add(rt<<1|1,seg[rt].D);
		if(seg[rt].U!=INF) remove(rt<<1,seg[rt].U),remove(rt<<1|1,seg[rt].U);
	}
	seg[rt].U=INF,seg[rt].D=0;
}

void modify(int L,int R,int l,int r,int rt,int x,int type)
{
	down(l,r,rt);
	if(L<=l && R>=r)
	{
		if(type==1) add(rt,x);
		else remove(rt,x);
		return;
	}
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,x,type);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,x,type);
}

void all(int l,int r,int rt,int finalHeight[])
{
	down(l,r,rt);
	if(l==r) return finalHeight[l]=seg[rt].D,void();
	int m=l+r>>1;
	all(l,m,rt<<1,finalHeight),all(m+1,r,rt<<1|1,finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<3*n;++i) seg[i].U=-1,seg[i].D=0;
	for(int i=0;i<k;++i) modify(left[i],right[i],0,n-1,1,height[i],op[i]);
	all(0,n-1,1,finalHeight);
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'void modify(int, int, int, int, int, int, int)':
wall.cpp:61:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
wall.cpp: In function 'void all(int, int, int, int*)':
wall.cpp:70:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

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