제출 #1144325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144325		arashmemar	Pyramid Base (IOI08_pyramid_base)	C++17	32 / 100	5102 ms	270128 KiB

pyramid_base

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

const int maxn = 1e6 + 100;
long long int inf = 3e9;
int n, m;

vector <pair <long long int, pair <int, int>>> seg[4 * maxn];
vector <pair <pair <pair <int, int>, pair <int, int>>, int>> ps;
long long int v[4 * maxn], lazy[4 * maxn];

struct Node
{
	void spread(int id, int L, int R)
	{
		v[id] += lazy[id];
		if (id * 2 < 4 * maxn)
		{
			lazy[id * 2 + 0] += lazy[id];
			lazy[id * 2 + 1] += lazy[id];
		}
		lazy[id] = 0;
		return ;
	}

	void updatep(int id, int L, int R, int l, int r, long long int val)
	{
		spread(id, L, R);
		if (L == l and R == r)
		{
			lazy[id] = val;
			spread(id, L, R);
			return ;
		}
		int mid = (L + R) / 2;
		if (l < mid)
		{
			updatep(id * 2 + 0, L, mid, l, min(mid, r), val);
		}
		if (r > mid)
		{
			updatep(id * 2 + 1, mid, R, max(l, mid), r, val);
		}
		spread(id * 2 + 0, L, mid);
		spread(id * 2 + 1, mid, R);
		v[id] = min(v[id * 2 + 0], v[id * 2 + 1]);
		return ;
	}
	
	long long int get()
	{
		spread(1, 1, n + 1);
		return v[1];
	}
};

Node *root;

void update(int id, int L, int R, int l, int r, long long int val, int ll, int rr)
{
	if (L == l and R == r)
	{
		seg[id].push_back({val, {ll, rr}});
		return ;
	}
	int mid = (L + R) / 2;
	if (l < mid)
	{
		update(id * 2 + 0, L, mid, l, min(r, mid), val, ll, rr);
	}
	if (r > mid)
	{
		update(id * 2 + 1, mid, R, max(l, mid), r, val, ll, rr);
	}
	return ;
}

void inc(int id)
{
	for (auto o : seg[id])
	{
		root->updatep(1, 1, n + 1, o.second.first, o.second.second, o.first);
	}
	return ;
}

void del(int id)
{
	for (auto o : seg[id])
	{
		root->updatep(1, 1, n + 1, o.second.first, o.second.second, -o.first);
	}
	return ;
}

long long int get(int id, int L, int R)
{
	inc(id);
	if (R - L == 1)
	{
		long long int ret = root->get();
		del(id);
		return ret;
	}
	int mid = (L + R) / 2;
	long long int ret = min(get(id * 2 + 0, L, mid), get(id * 2 + 1, mid, R));
	del(id);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int b, p;
	cin >> m >> n >> b >> p;

	root = new Node();

	int l = 0, r = min(n, m) + 1;

	for (int i = 0;i < p;i++)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		ps.push_back({{{y1, y2}, {x1, x2}}, c});
	}

	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		for (auto o : ps)
		{
			int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
			update(1, 1, m + 1, max(1, x1 - mid + 1), x2 + 1, c, max(1, y1 - mid + 1), y2 + 1);
		}

		if (mid > 1)
		{
			int y1 = m - mid + 1, y2 = m, x1 = 1, x2 = n;
			long long int c = inf;
			update(1, 1, m + 1, y1, y2 + 1, c, x1, x2 + 1);
			y1 = 1, y2 = m, x1 = n - mid + 1, x2 = n;
			update(1, 1, m + 1, y1, y2 + 1, c, x1, x2 + 1);
		}


		long long int tmp = get(1, 1, m + 1);
		if (tmp <= b)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
		for (int i = 0;i <= 4 * m;i++)
		{
			seg[i].clear();
		}
	}
	cout << l;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10