Submission #1279500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279500		AbdullahIshfaq	Inspections (NOI23_inspections)	C++20	100 / 100	603 ms	26848 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD 998244353
void solve()
{
	ll n, m, q, cnt = 0, l, r;
	map<ll, ll> mp, suff;
	cin >> n >> m >> q;
	mp[0] = -1;
	for (ll i = 1; i <= m; i++)
	{
		cin >> l >> r;
		l--;
		ll cur = cnt - l;
		cnt += r - l;
		mp.insert({l, prev(mp.upper_bound(l))->second});
		mp.insert({r, prev(mp.upper_bound(r))->second});
		auto L = mp.find(l), R = mp.find(r);
		while (L != R)
		{
			auto nxt = next(L);
			if (L->second != -1)
			{
				suff[cur - L->second] += nxt->first - L->first;
			}
			mp.erase(L);
			L = nxt;
		}
		mp[l] = cur;
	}
	ll tot = 0;
	suff[2e18] = 0;
	for (auto i = (--suff.end()); i != (--suff.begin()); i--)
	{
		tot += i->second;
		i->second = tot;
	}
	for (int i = 0; i != q; i++)
	{
		ll x;
		cin >> x;
		cout << suff.upper_bound(x)->second << " ";
	}
	cout << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++)
	{
		solve();
	}
	return 0;
}

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