제출 #1208510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208510		MuhammadSaram	Inspections (NOI23_inspections)	C++20	100 / 100	948 ms	49172 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define f first
#define s second

const int M = 6e5;

pair<pair<int,int>,ll> v[M],a;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL),cout.tie(NULL);
	
	int n,m,q;
	cin>>n>>m>>q;
	set<pair<pair<int,int>,ll>> se;
	map<ll,ll> suf;
	set<ll,greater<ll>> se1;
	ll t=0;
	for (int i=0;i<m;i++)
	{
		int l,r;
		cin>>l>>r;
		auto it=se.upper_bound({{l,0},0});
		int id=0;
		if (it!=se.begin())
		{
			it--;
			v[id++]=*it;
			it++;
		}
		while (it!=se.end() && (*it).f.f<=r)
			v[id++]=*it,it++;
		for (int j=0;j<id;j++)
		{
			a=v[j];
			int mn=max(a.f.f,l),mx=min(a.f.s,r);
			if (mn>mx) continue;
			ll dif=t+mn-l-(mn-a.f.f+a.s);
			suf[dif]+=mx-mn+1,se1.insert(dif);
			if (mn==a.f.f && mx==a.f.s)
				se.erase(a);
		}
		if (id)
		{
			a=v[0];
			if (a.f.f<l && a.f.s>=l)
				se.erase(a),se.insert({{a.f.f,l-1},a.s});
			a=v[id-1];
			if (a.f.s>r && a.f.f<=r)
				se.erase(a),se.insert({{r+1,a.f.s},a.s+r+1-a.f.f});
		}
		se.insert({{l,r},t});
		t+=r-l+1;
	}
	ll su=0,id=0;
	vector<pair<ll,ll>> ans(suf.size());
	for (ll i:se1)
		su+=suf[i],ans[id++]={i,su};
	sort(ans.begin(),ans.end());
	while (q--)
	{
		ll x;
		cin>>x;
		x=lower_bound(ans.begin(),ans.end(),make_pair(x+1,0ll))-begin(ans);
		if (x!=ans.size())
			cout<<ans[x].second<<' ';
		else	
			cout<<0<<' ';
	}
}

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