Submission #915970

#	Time	Username	Problem	Language	Result	Execution time	Memory
915970		pan	Inspections (NOI23_inspections)	C++17	0 / 100	239 ms	16248 KiB

Main

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;

ll n, m, q, l, r, t;
set<pi> s;
vector<ll> last;
vector<ll> ans;
vector<pi> works;
vector<pi> queries;
vector<ll> answer;

int main()
{
	t = 0;
	cin >> n >> m >> q;
	last.assign(n+5, -1);
	ans.assign(q+5,0);
	works.resize(m+5);
	answer.resize(q);
	queries.resize(q);
	s.insert(mp(1, n));;
	for (ll i=0; i<m; ++i) cin >> works[i].f >> works[i].s;
	for (ll i=0; i<q; ++i) {cin >> queries[i].f; queries[i].s = i;}
	sort(queries.begin(), queries.end());
	for (ll i=0; i<m; ++i)
	{
		
		ll midx = LLONG_MAX, midy = LLONG_MIN;
		vector<pi> toadd;
		ll l = works[i].f, r=  works[i].s;
		ll time = t+1-l;
		auto it = s.ub(mp(l, n+1));
		it--;
		//show2(l, r);
		while (it!=s.end() && !(((*it).s<l) || (*it).f>r))
		{
			ll x = (*it).f, y= (*it).s;
			//show2(x, y);
			ll range = min(y, r)-max(x, l)+1;
			ll bound = (t+1-l) - last[x];
			//show2(range, bound);
			auto add = ub(queries.begin(), queries.end(), mp(bound, 0LL))-queries.begin();
			if (last[x]!=-1)
			{
				ans[0]+=range;
				ans[add]-=range;
			}
			if (x<l && y>r)
			{
				toadd.pb(mp(x, l-1));
				toadd.pb(mp(r+1, y));
				toadd.pb(mp(l, r));
				last[r+1] = last[x];
				last[l] = time;
			}
			else if (x>=l && y<=r) // complete 
			{
				midx = min(midx, x);
				midy = max(midy, y);
			}
			else if (x<l)
			{
				toadd.pb(mp(x, l-1));
				toadd.pb(mp(l, y));
				last[l] = time;
			}
			else if (y>r)
			{
				toadd.pb(mp(x, r));
				toadd.pb(mp(r+1, y));
				last[r+1] = last[x];
				last[x] = time;
			}
			it = s.erase(it);
		}
		for (pi u: toadd) { s.insert(u);}
		if (midx!=LLONG_MAX && midy!=LLONG_MAX)
		{
			s.insert(mp(midx, midy));
			//show2(midx, midy);
			last[midx] = time;
		}
		//for (auto x = s.begin(); x!=s.end(); ++x) show2(x->f, x->s);
		t+=r-l+1;
	}
	for (ll i=0; i<q; ++i) 
	{
		if (i) ans[i]+=ans[i-1];
		answer[queries[i].s]=ans[i];
	}
	for (ll i=0; i<q; ++i) cout << answer[i] << ' ';
		
	
	return 0;
}

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