Submission #1313165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313165		miniob	Inspections (NOI23_inspections)	C++20	100 / 100	955 ms	87900 KiB

Main

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

struct przedzial
{
	long long l, r, ind, kiedy;
};

bool sfunkc(const przedzial a, const przedzial b)
{
	if (a.l != b.l)
	{
		return a.l < b.l;
	}
	if (a.r != b.r)
	{
		return a.r < b.r;
	}
	return a.ind < b.ind;
}

unordered_map<long long, long long> pref;
map<long long, long long> pref2;
vector<long long> co_zgasic[200007];
set<pair<long long, long long>> kiedy_u;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n, m, q, l, r, suma = 1100000000000;
	vector<przedzial> przedzialy;
	vector<przedzial> przedzialy_org;
	cin >> n >> m >> q;
	for (long long i = 0; i < m; i++)
	{
		cin >> l >> r;
		przedzial temp;
		temp.l = l;
		temp.r = r;
		temp.ind = i;
		temp.kiedy = suma - l + 2;
		//cout << temp.kiedy << endl;
		przedzialy.push_back(temp);
		przedzialy_org.push_back(temp);
		suma += r - l + 1;
	}
	sort(przedzialy.begin(), przedzialy.end(), sfunkc);

	long long it = 0;
	while (it < m && przedzialy[it].l == 1)
	{
		//cout << przedzialy[it].kiedy << " " << przedzialy[it].ind << endl;
		//cout << przedzialy[it].r + 1 << endl;
		kiedy_u.insert({ przedzialy[it].kiedy, przedzialy[it].ind });
		co_zgasic[przedzialy[it].r + 1].push_back(przedzialy[it].ind);
		it++;
	}
	long long pop = -1;
	kiedy_u.insert({ -1, -1 });
	for (auto x : kiedy_u)
	{
		if (x.first != -1)
		{
			if (pop == -1)
			{
				pop = x.first;
			}
			else
			{
				long long roz = x.first - pop - 1;
				pref[roz] += n;
				pop = x.first;
			}
		}
	}
	for (long long i = 2; i <= n; i++)
	{
		for (auto cur : co_zgasic[i])
		{
			auto it2 = kiedy_u.find({ przedzialy_org[cur].kiedy, cur });
			it2--;
			auto it3 = kiedy_u.upper_bound({ przedzialy_org[cur].kiedy, cur });
			if (it2 != kiedy_u.begin() && it3 != kiedy_u.end())
			{
				pref[przedzialy_org[cur].kiedy - (*it2).first - 1] -= (n - i + 1);
				pref[(*it3).first - przedzialy_org[cur].kiedy - 1] -= (n - i + 1);
				pref[(*it3).first - (*it2).first - 1] += (n - i + 1);
			}
			else if (it2 != kiedy_u.begin())
			{
				//cout << przedzialy_org[cur].kiedy << " " << cur << endl;
				pref[przedzialy_org[cur].kiedy - (*it2).first - 1] -= (n - i + 1);
			}
			else if (it3 != kiedy_u.end())
			{
				pref[(*it3).first - przedzialy_org[cur].kiedy - 1] -= (n - i + 1);
			}
			kiedy_u.erase(*(kiedy_u.find({ przedzialy_org[cur].kiedy, cur })));
		}
		while (it < m && przedzialy[it].l == i)
		{
			co_zgasic[przedzialy[it].r + 1].push_back(przedzialy[it].ind);
			long long cur = it;
			auto it3 = kiedy_u.upper_bound({ przedzialy[cur].kiedy, przedzialy[it].ind });
			auto it2 = prev(it3, 1);
			//cout << przedzialy[cur].kiedy << " " << przedzialy[it].ind << endl;
			/*for(auto x : kiedy_u)
			{
				cout << x.first << " " << x.second << endl;
			}*/
			if (it2 != kiedy_u.begin() && it3 != kiedy_u.end())
			{
				//cout << (*it3).first - (*it2).first - 1 << endl;
				pref[przedzialy[cur].kiedy - (*it2).first - 1] += (n - i + 1);
				pref[(*it3).first - przedzialy[cur].kiedy - 1] += (n - i + 1);
				pref[(*it3).first - (*it2).first - 1] -= (n - i + 1);
			}
			else if (it2 != kiedy_u.begin())
			{
				//cout << przedzialy[cur].kiedy << " " << przedzialy[cur].ind << endl;
				//cout << przedzialy[cur].kiedy - (*it2).first - 1 << endl;
				pref[przedzialy[cur].kiedy - (*it2).first - 1] += (n - i + 1);
			}
			else if (it3 != kiedy_u.end())
			{
				pref[(*it3).first - przedzialy[cur].kiedy - 1] += (n - i + 1);
			}
			//cout << endl;
			kiedy_u.insert({ przedzialy[it].kiedy, przedzialy[it].ind });
			it++;
		}
	}
	set<pair<long long, long long>> odp;
	odp.insert({ -1, -1 });
	long long popw = 0, maxx = 0, maxx2 = 0;
	for(auto it : pref)
	{
		pref2[it.first] = it.second;
	}
	for (auto it = pref2.rbegin(); it != pref2.rend(); it++)
	{
		pref2[it->first] += popw;
		popw = pref2[it->first];
		maxx2 = max(maxx2, pref2[it->first]);
		odp.insert({ it->first, it->second });
		maxx = max(maxx, it->first);
	}
	odp.insert({ 1000000000007, 0 });
	odp.insert({ 0, maxx2 });
	long long curq;
	for (long long i = 0; i < q; i++)
	{
		cin >> curq;
		auto it = odp.upper_bound({ curq, -1 });
		cout << (*it).second << " ";
	}
	cout << endl;
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 23 / 23