Submission #2601086

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

multiset<ll> M;
const ll INF = ll(1e16);

ll ans;
ll n,m,d; 

void add(ll x)
{
	M.insert(x);
	if(M.count(x)<2)
	{
		ans++;
		auto it = M.lower_bound(x);
		if(it!=M.begin()&&next(it)!=M.end())
		{
			ll tmp = (*next(it)) - (*prev(it)) - 1;
			if(tmp>=1&&tmp<=d) ans-=tmp;
		}
		if(it!=M.begin())
		{
			ll tmp = (*it)-(*prev(it))-1;
			if(tmp>=1&&tmp<=d) ans+=tmp;
		}
		if(next(it)!=M.end())
		{
			ll tmp = (*next(it)) - (*it) - 1;
			if(tmp>=1&&tmp<=d) ans+=tmp;
		}
	}
}

void del(ll x)
{
	auto it = M.find(x);
	if(it==M.end()) return ;
	if(M.count(x)<2)
	{	
		ans--;
		if(it!=M.begin())
		{
			ll tmp = (*it)-(*prev(it))-1;
			if(tmp>=1&&tmp<=d) ans-=tmp;
		}
		if(next(it)!=M.end())
		{
			ll tmp = (*next(it)) - (*it) - 1;
			if(tmp>=1&&tmp<=d) ans-=tmp;
		}
		if(it!=M.begin()&&next(it)!=M.end())
		{
			ll tmp = (*next(it)) - (*prev(it)) - 1;
			if(tmp>=1&&tmp<=d) ans+=tmp;
		}
	}
	M.erase(it);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	M.insert(-INF); M.insert(INF);
	ll y,w; cin>>y>>w;
	cin>>n>>m>>d;
	vector<ll> A;
	for(int i=0;i<n;i++)
	{
		ll x; cin>>x; A.pb(x);
	}
	ans = 0;
	vector<ii> events;
	for(int i=0;i<m;i++)
	{
		ll a,b; cin>>a>>b;
		a--;
		ll day = a*w + b;
		add(day);
		events.pb(mp(b, day));
	}
	sort(events.begin(),events.end());
	int ptr = 0;
	for(int i=1;i<=w;i++)
	{
		while(ptr<events.size()&&events[ptr].fi==i-1)
		{
			//cout<<"ANS "<<events[ptr].fi<<' '<<events[ptr].se<<' '<<ans<<'\n';
			del(events[ptr].se);
			add(events[ptr].se+w);
			//cout<<"ANS "<<ans<<'\n';
			ptr++;
		}
		//cout<<ans<<'\n';
		for(ll x:A)
		{
			add(x+i-1);
		}
		cout<<ans<<'\n';
		for(ll x:A)
		{
			del(x+i-1);
		}
	}
}

Submission Info

Judge Result