제출 #1173570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1173570		PenguinsAreCute	Inspections (NOI23_inspections)	C++20	100 / 100	566 ms	22880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<long long,long long>> ans;
	set<tuple<int,int,long long>> st;
	st.insert({1, n, 1LL<<40});
	long long time = 0;
	for(int i=0;i<m;i++) {
		int l, r;
		cin >> l >> r;
		auto it = st.lower_bound(make_tuple(l,0,0));
		if(it == st.end() || get<0>(*it) > l) {
			it--;
			auto [cl, cr, ct] = (*it);
			st.erase(it);
			st.insert({cl,l-1,ct});
			st.insert({l,cr,ct});
		}
		it = st.lower_bound(make_tuple(r+1,0,0));
		it--;
		if(get<1>(*it) > r) {
			auto [cl, cr, ct] = (*it);
			st.erase(it);
			st.insert({cl,r,ct});
			st.insert({r+1,cr,ct});
		}
		long long cur = time - l;
		while(1) {
			it = st.lower_bound(make_tuple(l,0,0));
			if(it == st.end() || get<0>(*it) > r)
				break;
			auto [cl, cr, ct] = (*it);
			ans.push_back({cur - ct, cr - cl + 1});
			st.erase(it);
		}
		st.insert({l,r,cur});
		time += (r - l + 1);
	}
	sort(ans.begin(),ans.end());
	for(int i = int(ans.size());--i;)
		ans[i-1].second += ans[i].second;
	while(q--) {
		long long s;
		cin >> s;
		auto it = lower_bound(ans.begin(),ans.end(),make_pair(s+1,0LL));
		if(it == ans.end())
			cout << "0 ";
		else
			cout << it->second << " ";
	}
}

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