제출 #197711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197711		arnold518	벽 (IOI14_wall)	C++14	100 / 100	893 ms	106232 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;
const int MAXK = 5e5;
const int INF = 987654321;

int N, K;
int O[MAXK+10], L[MAXK+10], R[MAXK+10], H[MAXK+10], ans[MAXN+10];

struct Node
{
	int l, r;
	Node() : l(0), r(INF) {}
	Node(int l, int r) : l(l), r(r) {}
};

Node tree[MAXN*4+10];

Node operator + (const Node &p, const Node &q)
{
	if(q.r<=p.l) return Node(q.r, q.r);
	if(p.r<=q.l) return Node(q.l, q.l);
	return Node(max(p.l, q.l), min(p.r, q.r));
}

void update(int node, int tl, int tr, int l, int r, int k)
{
	if(tl!=tr)
	{
		tree[node*2]=tree[node*2]+tree[node];
		tree[node*2+1]=tree[node*2+1]+tree[node];
		tree[node]=Node();
	}
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		Node t;
		if(O[k]==1) t.l=H[k];
		if(O[k]==2) t.r=H[k];
		tree[node]=tree[node]+t;
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
}

void query(int node, int tl, int tr)
{
	if(tl!=tr)
	{
		tree[node*2]=tree[node*2]+tree[node];
		tree[node*2+1]=tree[node*2+1]+tree[node];
		tree[node]=Node();
	}
	else
	{
		ans[tl]=tree[node].l;
		return;
	}
	int mid=tl+tr>>1;
	query(node*2, tl, mid);
	query(node*2+1, mid+1, tr);
}

void buildWall(int _N, int _K, int *_O, int *_L, int *_R, int *_H, int finalHeight[])
{
	int i, j;

	N=_N; K=_K;
	for(i=1; i<=K; i++) O[i]=_O[i-1], L[i]=_L[i-1]+1, R[i]=_R[i-1]+1, H[i]=_H[i-1];

	for(i=1; i<=K; i++) update(1, 1, N, L[i], R[i], i);
	query(1, 1, N);
	for(i=1; i<=N; i++) finalHeight[i-1]=ans[i];
}

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

wall.cpp: In function 'void update(int, int, int, int, int, int)':
wall.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void query(int, int, int)':
wall.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:74:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

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