Submission #2601663

---

Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<lint,lint> pint;
typedef pair<pint,int> tint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
set<tint> s;
vector<int> ch[100100];
lint nb[58],nc[58];
lint out,y,w,d;
lint cal(set<tint>::iterator it){
	return (*it).fi.fi*w+(*it).fi.se;
}
void del(lint B,lint C,int x){
	set<tint>::iterator it=s.lower_bound(mp(mp(B,C),x)),itl=it,ith=it;
	itl--;ith++;
	lint a=cal(itl),b=cal(it),c=cal(ith);
	if(b==a) out++;else if(b-a-1<=d) out-=max(0LL,b-a-1);
	if(c==b) out++;else if(c-b-1<=d) out-=max(0LL,c-b-1);
	if(a==c) out--;else if(c-a-1<=d) out+=max(0LL,c-a-1);
	s.erase(it);
}
void ins(lint B,lint C,int x){
	s.insert(mp(mp(B,C),x));
	set<tint>::iterator it=s.lower_bound(mp(mp(B,C),x)),itl=it,ith=it;
	itl--;ith++;
	lint a=cal(itl),b=cal(it),c=cal(ith);
	if(b==a) out--;else if(b-a-1<=d) out+=max(0LL,b-a-1);
	if(c==b) out--;else if(c-b-1<=d) out+=max(0LL,c-b-1);
	if(c==a) out++;if(c-a-1<=d) out-=max(0LL,c-a-1);
}
void outp(){
	set<tint>::iterator it=s.begin();
	while(it!=s.end()){
		cout<<(*it).fi.fi<<','<<(*it).fi.se<<','<<(*it).se<<' ';it++;
	}
	cout<<endl;
}
int main()
{
	lint b,c,inf=123456789012345678LL;int n,m;
	cin>>y>>w;cin>>n>>m>>d;
	rep(i,n){
		cin>>b;b--;
		nb[i]=b/w;nb[i]++;nc[i]=b%w;nc[i]++;
		s.insert(mp(mp(nb[i],nc[i]),0));
	}
	//outp();
	rep(i,m){
		cin>>b>>c;
		s.insert(mp(mp(b,c),1));
		ch[c].pb(b);
	}
	s.insert(mp(mp(-1,-inf),0));s.insert(mp(mp(1001001001,inf),0));
	out=m+n;
	set<tint>::iterator it=s.begin();
	while(it!=s.end()){
		set<tint>::iterator it2=it;it2++;
		lint lo=cal(it),hi=cal(it2);
		if(hi==lo) out--;else if(hi-lo-1<=d) out+=max(0LL,hi-lo-1);
		it++;
	}
	REP(i,1,w+1){
		cout<<out<<endl;
		rep(j,ch[i].size()){
			del(ch[i][j],i,1);ins(ch[i][j],i+w,1);
		}
		rep(j,n){
			del(nb[j],nc[j],0);nc[j]++;ins(nb[j],nc[j],0);
		}
	}
}

Submission Info

Judge Result