Submission #2601703

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long Int;
vector<Int> week[108000];
multiset<Int> holiday;
Int y, w, n, m, d, b, c, a[108000];
Int res;
void add_holiday(Int x){
	if(holiday.count(x)){
		holiday.insert(x);
		return;
	}
	Int left = -1;
	Int right = -1;
	multiset<Int>::iterator it;

	it = holiday.upper_bound(x);
	if(it != holiday.end())right = *it;
	if(it != holiday.begin())left = *(--it);
	holiday.insert(x);
	if(left != -1 && right != -1 && (right - left -1) <= d)return;
	res++;
	if(left != -1 && x - left - 1 <= d)res += x-left-1;
	if(right != -1 && right - x - 1 <= d)res += right-x-1;
	return;
}

void rm_holiday(Int x){
	if(holiday.count(x)>1 ){
		holiday.erase(holiday.find(x));
		return;
	}
	Int left = -1;
	Int right = -1;
	multiset<Int>::iterator it;
	it = holiday.upper_bound(x);
	if(it != holiday.end())right = *it;
	it = holiday.lower_bound(x);
	if(it != holiday.begin())left = *(--it);
	holiday.erase(x);
	if(left != -1 && right != -1 && (right - left -1) <= d)return;
	res--;
	if(left != -1 && x - left - 1 <= d)res -= x-left-1;
	if(right != -1 && right - x - 1 <= d)res -= right-x-1;
	return;
}

int main(){
	cin >> y >> w;
	cin >> n >> m >> d;
	for(Int i = 0;i < n;i++){
		cin >> a[i],a[i]--;
		add_holiday(a[i]);
	}
	for(Int i = 0;i < m;i++){
		cin >> b >> c;b--,c--;
		week[c].push_back(b);
		add_holiday(w*b+c);
	}
	for(Int i = 0;i < w;i++){
		cout << res << endl;
		for(Int j = 0;j < week[i].size();j++){
			int ww = week[i][j];
			rm_holiday(ww*w+i);
			add_holiday((ww+1)*w+i);
		}
		for(Int j = 0;j < n;j++){
			rm_holiday(a[j]+i);
			add_holiday(a[j]+i+1);
		}
	}
	return 0;
}

Submission Info

Judge Result