Submission #1144310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144310		arashmemar	Pyramid Base (IOI08_pyramid_base)	C++20	32 / 100	5100 ms	327680 KiB

pyramid_base

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

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

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

struct Node
{
	int L, R, mid;
	long long int v, lazy;
	Node *lc, *rc;

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = lazy = 0, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		return ;
	}

	void spread()
	{
		v += lazy;
		if (lc != NULL)
		{
			lc->lazy += lazy;
			rc->lazy += lazy;
		}
		lazy = 0;
		return ;
	}

	void update(int l, int r, long long int val)
	{
		spread();
		if (L == l and R == r)
		{
			lazy = val;
			spread();
			return ;
		}
		if (l < mid)
		{
			lc->update(l, min(mid, r), val);
		}
		if (r > mid)
		{
			rc->update(max(l, mid), r, val);
		}
		lc->spread();
		rc->spread();
		v = min(lc->v, rc->v);
		return ;
	}
	
	long long int get()
	{
		spread();
		return v;
	}
};

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->update(o.second.first, o.second.second, o.first);
	}
	return ;
}

void del(int id)
{
	for (auto o : seg[id])
	{
		root->update(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 n, m, b, p;
	cin >> m >> n >> b >> p;

	root = new Node(1, n + 1);
	root->init();

	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});
		if (b == 0)
		{
			r = min(r, max(max(max(m - y1, m - y2), max(y1, y2)), max(max(n - x1, n - x2), max(x1, x2))));
		}
	}

	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 << endl;
}

• 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