Submission #832648

#	Time	Username	Problem	Language	Result	Execution time	Memory
832648		gustason	Inspections (NOI23_inspections)	C++14	29 / 100	2091 ms	14652 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, q;
	cin >> n >> m >> q;
	
	vector<pair<int, int>> a(m);
	vector<ll> s(q);
	for(auto& i : a) {
		cin >> i.first >> i.second;
	}
	
	for(auto& i : s) {
		cin >> i;
	}
	
	map<int, int> prev;
	map<int, int> mp;
	
	int t = 1;
	for(int i = 0; i < m; i++) {
		for(int j = a[i].first; j <= a[i].second; j++, t++) {
			if (prev.find(j) != prev.end()) {
				mp[t-prev[j]-1]++;
			}
			prev[j] = t;
		} 
	}	

	map<int, int> cnt;
	int sum = 0;
	for(auto& i : mp) {
		cnt[i.first] = sum + i.second;
		sum += i.second;
	}
	//for(auto& i : cnt) {
		//cout << i.first << " " << i.second << "\n";
	//}
		
	for(int i = 0; i < q; i++) {
		auto it = cnt.lower_bound(s[i]);
		if (it == cnt.begin()) {
			cout << sum << " ";
			continue;
		}
		it--;
		cout << sum - it->second << " "; 
	}
}

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