제출 #395432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395432		Aryan_Raina	Wall (IOI14_wall)	C++14	100 / 100	1394 ms	64224 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
	int size = 1;
	vector<int> mx, mn;
	SegTree(int n) {
		while (size < n) size <<= 1;
		mx.resize(2*size, 0); mn.resize(2*size, 0);
	}

	void modify_op(int x, int t, int v) {
		if (t == 1) {
			mn[x] = max(mn[x], v);
			mx[x] = max(mx[x], v);
		} else if (t == 2) {
			mn[x] = min(mn[x], v);
			mx[x] = min(mx[x], v);
		}
	}

	void propagate(int x, int lx, int rx) {
		if (rx - lx == 1) return;
		modify_op(2*x+1, 1, mn[x]);
		modify_op(2*x+2, 1, mn[x]);
		modify_op(2*x+1, 2, mx[x]);
		modify_op(2*x+2, 2, mx[x]);
	}

	void modify(int l, int r, int t, int v, int x, int lx, int rx) {
		propagate(x, lx, rx);
		if (r <= lx || rx <= l) return;
		if (l <= lx && rx <= r) return modify_op(x, t, v);
		int m = (lx + rx) >> 1;
		modify(l, r, t, v, 2*x+1, lx, m); modify(l, r, t, v, 2*x+2, m, rx);
		mx[x] = max(mx[2*x+1], mx[2*x+2]);
		mn[x] = min(mn[2*x+1], mn[2*x+2]);
	}
	void modify(int l, int r, int t, int v) { modify(l, r, t, v, 0, 0, size); }

	void calc(vector<int> &a, int x, int lx, int rx) {
		propagate(x, lx, rx);
		if (rx - lx == 1) {
			if (lx < a.size()) a[lx] = mn[x];
			return;
		}
		int m = (lx + rx) >> 1;
		calc(a, 2*x+1, lx, m); calc(a, 2*x+2, m, rx);
	}
	void calc(vector<int> &a) { return calc(a, 0, 0, size); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree st(n);
	for (int i = 0; i < k; i++) {
		st.modify(left[i], right[i]+1, op[i], height[i]);
	}
	vector<int> a(n); st.calc(a);
	for (int i = 0; i < n; i++) finalHeight[i] = a[i];
	return;
}

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

wall.cpp: In member function 'void SegTree::calc(std::vector<int>&, int, int, int)':
wall.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    if (lx < a.size()) a[lx] = mn[x];
      |        ~~~^~~~~~~~~~

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