Submission #929235

#	Time	Username	Problem	Language	Result	Execution time	Memory
929235		ono_de206	Inspections (NOI23_inspections)	C++14	0 / 100	887 ms	44692 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
// typedef pair<int, int> P;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}

template<typename T, typename U>
	istream & operator >> (istream &in, pair<T, U> &c) {
	in >> c.first;
	in >> c.second;
	return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523, N = 2500;
const long long inf = 2e18 + 10;
int l[mxn], r[mxn], qry[mxn], pre[mxn];
map<int, int> mp;
vector<int> add[mxn], rem[mxn];
set<int> s;
int now, n;

int get(int le, int ri) {
	return pre[ri - 1] - pre[le] + r[le] - l[ri];
}

void insert(int id) {
	int le = -1, ri = -1;
	auto it = s.lower_bound(id);
	if(it != s.end()) ri = *it;
	if(it != s.begin()) le = *prev(it);
	if(le != -1 && ri != -1) {
		int x = get(le, ri);
		mp[-x] -= (n - now + 1);
	}
	if(le != -1) {
		int x = get(le, id);
		mp[-x] += (n - now + 1);
	}
	if(ri != -1) {
		int x = get(id, ri);
		mp[-x] += (n - now + 1);
	}
	s.in(id);
}

void erase(int id) {
	s.erase(id);
	int le = -1, ri = -1;
	auto it = s.lower_bound(id);
	if(it != s.end()) ri = *it;
	if(it != s.begin()) le = *prev(it);
	if(le != -1 && ri != -1) {
		int x = get(le, ri);
		mp[-x] += (n - now + 1);
	}
	if(le != -1) {
		int x = get(le, id);
		mp[-x] -= (n - now + 1);
	}
	if(ri != -1) {
		int x = get(id, ri);
		mp[-x] -= (n - now + 1);
	}
}

void go() {
	int m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= m; i++) {
		cin >> l[i] >> r[i];
		add[l[i]].eb(i);
		rem[r[i] + 1].eb(i);
	}
	for(int i = 1; i <= m; i++) {
		pre[i] = pre[i - 1] + (r[i] - l[i] + 1);
	}
	for(int i = 1; i <= n; i++) {
		now = i;
		for(int id : rem[i]) {
			erase(id);
		}
		for(int id : add[i]) {
			insert(id);
		}
		
	}
	for(int i = 1; i <= q; i++) {
		cin >> qry[i];
		mp[-qry[i]] += 0;
	}
	int ls = 0;
	for(auto &it : mp) {
		it.ss += ls;
		ls = it.ss;
	}
	for(int i = 1; i <= q; i++) {
		cout << mp[-qry[i]] << ' ';
	}
	cout << endl;
}

signed main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

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