Submission #1145106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145106		arashmemar	Pyramid Base (IOI08_pyramid_base)	C++20	100 / 100	1976 ms	169128 KiB

pyramid_base

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

const int maxn = 1e6 + 5e4;
int inf = 2e9;
int n, m;

vector <pair <int, pair <int, int>>> add[2 * maxn], rem[2 * maxn];
pair <pair <pair <int, int>, pair <int, int>>, int> ps[maxn];

int mv[2 * maxn], mvs[2 * maxn], mvsl[2 * maxn], mvsr[2 * maxn], lazyy[2 * maxn];

void init(int id, int L, int R)
{
	if (R - L == 1)
	{
		mv[id] = 0;
		mvs[id] = 1;
		mvsl[id] = 1;
		mvsr[id] = 1;
		return ;
	}
	int mid = (L + R) / 2;
	init(id * 2 + 0, L, mid);
	init(id * 2 + 1, mid, R);
	mv[id] = 0;
	mvs[id] = R - L;
	mvsl[id] = R - L;
	mvsr[id] = R - L;
	return ;
}

void spreadp(int id)
{
	mv[id] += lazyy[id];
	if (id < maxn)
	{
		lazyy[id * 2 + 0] += lazyy[id];
		lazyy[id * 2 + 1] += lazyy[id];
	}
	lazyy[id] = 0;
	return ;
}

void updatepp(int id, int L, int R, int l, int r, int val)
{
	if (L == l and R == r)
	{
		lazyy[id] += val;
		spreadp(id);
		return ;
	}
	spreadp(id);
	int mid = (L + R) / 2;
	if (l < mid)
	{
		updatepp(id * 2 + 0, L, mid, l, min(r, mid), val);
	}
	if (r > mid)
	{
		updatepp(id * 2 + 1, mid, R, max(l, mid), r, val);
	}
	spreadp(id * 2 + 0);
	spreadp(id * 2 + 1);
	mv[id] = min(mv[id * 2 + 0], mv[id * 2 + 1]);
	if (mv[id * 2 + 0] == mv[id] and mv[id * 2 + 1] != mv[id])
	{
		mvs[id] = mvs[id * 2 + 0];
		mvsl[id] = mvsl[id * 2 + 0];
		mvsr[id] = 0;
	}
	if (mv[id * 2 + 0] != mv[id] and mv[id * 2 + 1] == mv[id])
	{
		mvs[id] = mvs[id * 2 + 1];
		mvsl[id] = 0;
		mvsr[id] = mvsr[id * 2 + 1];
	}
	if (mv[id * 2 + 0] == mv[id * 2 + 1])
	{
		mvs[id] = max(max(mvs[id * 2 + 0], mvs[id * 2 + 1]), mvsl[id * 2 + 1] + mvsr[id * 2 + 0]);
		mvsl[id] = mvsl[id * 2 + 0];
		if (mvsl[id] == mid - L)
		{
			mvsl[id] += mvsl[id * 2 + 1];
		}
		mvsr[id] = mvsr[id * 2 + 1];
		if (mvsr[id] == R - mid)
		{
			mvsr[id] += mvsr[id * 2 + 0];
		}
	}
	return ;
}

int getpp()
{
	return mvs[1];
}

long long int v[2 * maxn], lazy[2 * maxn];

void spread(int id)
{
	v[id] += lazy[id];
	if (id < 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)
{
	if (L == l and R == r)
	{
		lazy[id] += val;
		spread(id);
		return ;
	}
	spread(id);
	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);
	}
	if (l >= mid)
	{
		spread(id * 2 + 0);
	}
	if (r <= mid)
	{
		spread(id * 2 + 1);
	}
	v[id] = min(v[id * 2 + 0], v[id * 2 + 1]);
	return ;
}

long long int getp()
{
	return v[1];
}

pair <int, int> update(int id, int L, int R, int l, int r)
{
	if (L == l and R == r)
	{
		return {id, id};
	}
	int mid = (L + R) / 2;
	pair <int, int> ret, tmp;
	ret = tmp = {0, 0};
	if (l < mid)
	{
		ret = update(id * 2 + 0, L, mid, l, min(r, mid));
	}
	if (r > mid)
	{
		tmp = update(id * 2 + 1, mid, R, max(l, mid), r);
		ret.second = tmp.second;
		if (ret.first == 0)
		{
			ret.first = tmp.first;
		}
	}
	return ret;
}

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

void del(int id)
{
	for (auto o : rem[id])
	{
		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 = getp();
		del(id);
		return ret;
	}
	int mid = (L + R) / 2;
	long long int tmp1 = get(id * 2 + 0, L, mid);
	long long int tmp2 = get(id * 2 + 1, mid, R);

	long long int ret = min(tmp1, tmp2);
	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;

	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[i] = {{{y1, y2}, {x1, x2}}, c};
	}

	if (b == 0)
	{
		init(1, 1, n + 1);
		for (int i = 0;i < p;i++)
		{
			auto o = ps[i];
			int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
			swap(x1, y1);
			swap(x2, y2);
			add[y1].push_back({i, {x1, x2 + 1}});
			rem[y2].push_back({i, {x1, x2 + 1}});
		}

		add[m + 1].push_back({-1, {1, n + 1}});

		int ptr = 1, ans = 0;

		for (int i = 1;i <= m;i++)
		{
//			cout << i << endl;
			for (auto o : add[ptr])
			{
//				cout << "update : " << o.second.first << ' ' << o.second.second << ' ' << 1 << ' ' << o.first << " : " << flush;
				updatepp(1, 1, n + 1, o.second.first, o.second.second, 1);
//				cout << getpp() << ' ' << mv[1] << endl;
			}
			while (getpp() > ans and mv[1] == 0)
			{
//				cout << "++" << endl;
				ptr++;
				ans++;
				for (auto o : add[ptr])
				{
//					cout << "updatep : " << o.second.first << ' ' << o.second.second << ' ' << 1 << ' ' << o.first << " : " << flush;
					updatepp(1, 1, n + 1, o.second.first, o.second.second, 1);
//					cout << getpp() << ' ' << mv[1] << endl;
				}
			}
			for (auto o : rem[i])
			{
//				cout << "update : " << o.second.first << ' ' << o.second.second << ' ' << -1 << ' ' << o.first << " : " << flush;
				updatepp(1, 1, n + 1, o.second.first, o.second.second, -1);
//				cout << getpp() << ' ' << mv[1] << endl;
			}
			ptr++;
		}

		cout << ans;
		return 0;
	}

	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		for (int i = 0;i < p;i++)
		{
			auto o = ps[i];
			int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
			pair <int, int> tmp = update(1, 1, m + 1, max(1, x1 - mid + 1), x2 + 1);
			add[tmp.first].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
			rem[tmp.second].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
		}

		if (mid > 1)
		{
			int y1 = m - mid + 2, y2 = m, x1 = 1, x2 = n;
			int c = inf;
			pair <int, int> tmp = update(1, 1, m + 1, y1, y2 + 1);
			add[tmp.first].push_back({c, {x1, x2 + 1}});
			rem[tmp.second].push_back({c, {x1, x2 + 1}});
			y1 = 1, y2 = m, x1 = n - mid + 2, x2 = n;
			tmp = update(1, 1, m + 1, y1, y2 + 1);
			add[tmp.first].push_back({c, {x1, x2 + 1}});
			rem[tmp.second].push_back({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 < 2 * maxn;i++)
		{
			add[i].clear();
			rem[i].clear();
			v[i] = lazy[i] = 0;
		}
	}
	cout << l;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 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: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10