DCRTIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Data Structures, Segment Trees

PROBLEM:

There are N stores in the mall (represented by a line), the i-th of which is located at point P_i, is of type D_i and appears in the interval [L_i,R_i] of time. We know that there are K types of stores in total. You are given Q queries of form (X_j,T_j). For each query we consider that we are initially in the position X_j and we want to visit all K types of stores (not necessarily all the stores, just at least one from each type) using minimum amount of walking. Whenever we visit a store we go back to position X_j and then we can go visit another store or if we had visited all the stores, we could go home. When considering the j-th query we should only take into account such stores i that L_i \le T_j \le R_i. Output the minimum amount that we’ll have to walk for each query. If it’s not possible to visit all the stores, output -1.

QUICK EXPLANATION

  • We can solve the problem independently for each type of stores. So from now on we assume all stores are of the same type. So we have to find the nearest available store for each query.
  • If at time T_j there were no available stores, the answer is -1. Otherwise it’s not.
  • For any query j the only two possible candidates for the nearest store (among all those who are available at time T_j) are the first stores to the left and right of point X_j.
  • At a fixed time, if there are two stores a and b such that there’s no other store between them and P_a \le P_b, then the a-th store will be the answer for all P_a \le X \le \frac{P_a+P_b}{2} and the b-th store for all \frac{P_a+P_b}{2} \le X \le P_b.
  • We can process all events (openings of stores, closings of stores and queries) in increasing order of time. So now we have to focus on adding a store, removing an existing store and finding the closest store to a point X. We can keep track of the stores in a set and to answer a query we can simply find the first stores to the left and right of X (by binary search) and see which one is the closer one.
  • So now we can find the closest store of a fixed type to X. In order to keep track of the sum of distances for all the types we should realize that distance of a store p to X which is |X-p|, is actually either X-p or p-X. So for a fixed X we can keep track of the coefficient of X and the signed sum of p.
  • Since we already know all the values of X, we can sort them in increasing order. Now an interval of form [P_a,\frac{P_a+P_b}{2}] is now an interval in an array of X. So a store only updates the value of a segment. So we can keep track of this value for all X using the above trick by two segment trees.

EXPLANATION

We can solve the problem independently for each type of store since their events are independent of each other. So from now on we assume all stores are of the same type and we should just find the nearest available store for each query. Since all the queries and stores are given to us in advance, we can solve the problem offline. Thus we can process all events (openings of stores, closings of stores and queries) in increasing order of their time. So now we have to focus on adding a store, removing an existing store and answering a query at point X.
It’s easy to see that the closest store to a point X is either the first store to it’s right or to it’s left. Now assume that there are two stores a and b such that P_a \le P_b and there’s no store between them. It’s easy to see that for all X \in [P_a, \frac{P_a+P_b}{2}] the closest store to X will be the a-th store. Similarly for all X \in [\frac{P_a+P_b}{2}, P_b] the closest store to X will be the b-th store. So we can find the distance of the closest available store to X (by using binary search on the set of the available stores).
Now back to the original problem (with different types of stores). We can keep track of the stores of each type in a different set and do the same thing we did before. However finding the closest store of each type for a query will be too slow. We can speed up this process by using the fact that each store i will only be useful for an interval of X. Namely suppose the first stores of type D_a to the left and right of store a to be the x-th and y-th store respectively. Then store a will only affect such X that X \in [\frac{P_x+P_a}{2},\frac{P_a+P_y}{2}]. So for each query j such that X_j \in [\frac{P_x+P_a}{2},\frac{P_a+P_y}{2}], we can add the distance of the a-th store and X_j to the current result of j since it’s optimal for it to visit the a-th store (among all stores of type D_a). Assuming that we have already sorted the queries according to their positions on the line, the a-th store will only affect a segment of this queries (which we will handle with segment trees or any similar data structures). Our only problem is that the distance of the a-th store is different to each query of this segment. In order to solve this issue, one must realize that the distance of to a-th store to position X_j is either X_j - P_a or P_a - X_j (depending on whether X_j \le P_a or not). So for all X \in [\frac{P_x+P_a}{2},P_a], the distance is P_a - X. As it happens, we can keep track of the distance in this form (c \times X + p) easily as we can keep two different segment trees, one for values of c and one for p. Thus we can answer each query using these two segment tress and the values stored in them.

Refer to the implementations for more details.

TIME COMPLEXITY

The time complexity is O((N + Q) \times log(Q) + N \times log(N)) with a rather heavy constant factor.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define mid (l + r >> 1)
using namespace std;
const int N = 300005, INF = 2e9 + 9;
int n, q, k, bad, A[N], T[N], P[N], D[N], L[N], R[N], S[N], Rev[N];
long long Res[N];
pair < int , long long > FN[N];
vector < int > U, VS[N * 2], VE[N * 2], VQ[N * 2];
multiset < int > ST[N];
inline void Add(int le, int ri, int cx, long long cp)
{
	for (le ++; le < N; le += le & - le)
		FN[le].first += cx, FN[le].second += cp;
	for (ri ++; ri < N; ri += ri & - ri)
		FN[ri].first -= cx, FN[ri].second -= cp;
}
inline pair < int , long long > Get(int i)
{
	pair < int , long long > rt = {0, 0};
	for (i ++; i; i -= i & - i)
		rt.first += FN[i].first,
		rt.second += FN[i].second;
	return (rt);
}
inline bool CMP(int i, int j)
{
	return (A[i] < A[j]);
}
inline void Do(int l, int r, int tp)
{
	int m = ((long long)l + r) >> 1, le, ri, md;
	A[0] = l; le = lower_bound(S + 1, S + q + 1, 0, CMP) - S;
	A[0] = r; ri = upper_bound(S + 1, S + q + 1, 0, CMP) - S;
	A[0] = m; md = upper_bound(S + 1, S + q + 1, 0, CMP) - S;
	Add(le, md, tp, - tp * l);
	Add(md, ri, - tp, tp * r);
}
inline void Ins(int d, int p)
{
	if ((int)ST[d].size() == 2)
		bad --;
	auto it = ST[d].lower_bound(p);
	if (* it == p)
		return void(ST[d].insert(p));
	int l, r;
	r = * it; it --; l = * it;
	ST[d].insert(p);
	Do(l, r, -1);
	Do(l, p, 1);
	Do(p, r, 1);
}
inline void Del(int d, int p)
{
	auto it = ST[d].lower_bound(p);
	it = ST[d].erase(it);
	if ((int)ST[d].size() == 2)
		bad ++;
	if (* it == p)
		return ;
	int l, r;
	r = * it; it --; l = * it;
	Do(l, p, -1);
	Do(p, r, -1);
	Do(l, r, 1);
}
int main()
{
	scanf("%d%d%d", &n, &q, &k);
	for (int i = 1; i <= n; i ++)
		scanf("%d%d%d%d", &P[i], &D[i], &L[i], &R[i]),
		R[i] ++, U.push_back(L[i]), U.push_back(R[i]);
	U.push_back(0);
	sort(U.begin(), U.end());
	U.resize(unique(U.begin(), U.end()) - U.begin());
	for (int i = 1; i <= n; i ++)
	{
		L[i] = (int)(lower_bound(U.begin(), U.end(), L[i]) - U.begin());
		R[i] = (int)(lower_bound(U.begin(), U.end(), R[i]) - U.begin());
		VS[L[i]].push_back(i);
		VE[R[i]].push_back(i);
	}
	for (int i = 1; i <= q; i ++)
	{
		scanf("%d%d", &A[i], &T[i]);
		T[i] = (int)(upper_bound(U.begin(), U.end(), T[i]) - U.begin()) - 1;
		VQ[T[i]].push_back(i);
		S[i] = i;
	}
	sort(S + 1, S + q + 1, CMP);
	for (int i = 1; i <= q; i ++)
		Rev[S[i]] = i;
	bad = k;
	for (int i = 1; i <= k; i ++)
		ST[i].insert(-INF), ST[i].insert(INF);
	Add(1, q + 1, -k, INF * 1LL * k);
	for (int i = 0; i <= (int)U.size(); i ++)
	{
		for (int id : VE[i])
			Del(D[id], P[id]);
		for (int id : VS[i])
			Ins(D[id], P[id]);
		for (int id : VQ[i])
		{
			if (bad)
				{Res[id] = -1; continue;}
			pair < int , long long > rt = Get(Rev[id]);
			Res[id] = rt.first * 1LL * A[id] + rt.second;
		}
	}
	for (int i = 1; i <= q; i ++)
		printf("%lld\n", Res[i]);
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
 
using namespace :: std;
 
 
//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
//=======================================================================//
 
 
 
const ll maxn=1e6+500;
const ll inf=1e9+800;
 
 
struct Seg{
	long long lazyC[maxn*4];
	long long lazyV[maxn*4];
	long long s;
	void bild(){
		s=0;
		memset(lazyV,0,sizeof lazyV);
		memset(lazyC,0,sizeof lazyC);
	}
	void begzar(ll t){
		s+=t;
	}
	void updateC(ll L,ll R,ll node,ll l,ll r,ll C){
		if(l<=L && R<=r){
			lazyC[node]+=C;
			lazyV[node]-=C*s;
			return;
		}
		if(r<=L || R<=l){
			return ;
		}
		ll mid=(L+R)/2;
		updateC(L,mid,2*node,l,r,C);
		updateC(mid,R,2*node+1,l,r,C);
	}
	void updateK(ll L,ll R,ll node,ll l,ll r,ll C){
		if(l<=L && R<=r){
			lazyV[node]+=C;
			return;
		}
		if(r<=L || R<=l){
			return ;
		}
		ll mid=(L+R)/2;
		updateK(L,mid,2*node,l,r,C);
		updateK(mid,R,2*node+1,l,r,C);
	}
	long long findVal(ll L,ll R,ll node,ll x){
		long long ans=lazyC[node]*s+lazyV[node];
		if(L+1==R){
			return ans;
		}
		ll mid=(L+R)/2;
		if(x<mid){
			ans+=findVal(L,mid,2*node,x);
		}else{
			ans+=findVal(mid,R,2*node+1,x);
		}
		return ans;
	}
};
 
 
 
 
 
 
struct  Store{
	ll p,d,l,r;
};
struct Event{
	ll l,r,x,c;
};
 
Seg R,W;
 
 
 
vector<Event> Ev;
vector<Event> firstt;
 
void add(ll l,ll r,ll L,ll R){
	Event a;
	a.l=l;
	a.r=r;
	a.x=(L+R);
	a.c=-2;
 
	if(L==0){
		a.c='+';
		a.x=R;
		firstt.pb(a);
	}else if(R<1000*1000*1000){
		Ev.pb(a);
	}
	if(R<1000*1000*1000){
		a.x=2*R;
		a.c=+2;
		Ev.pb(a);
	}
}
vector<Store> a[maxn];
inline bool cmp(Store a,Store b){
	return a.p<b.p;
}
inline bool cmpp(Event a,Event b){
	return a.x<b.x;
}
void addImp(vector<Store> &vec){
	sort(vec.begin(),vec.end(),cmp);
 
	set<pii> st;
	st.insert(mp(-inf,0));
	for(auto v:vec){
		auto it=st.lower_bound(mp(v.l,0));
		auto itt=it;
		itt--;
		pii omghl=(*itt);
		vector<pii> ves;
		while(it!=st.end() && (*it).F<v.r){
			ves.pb(*it);
			it++;
		}
		if(ves.size()){
			add(v.l,ves[0].F,omghl.S,v.p);
			for(ll i=1;i<(ll)ves.size();i++){
				add(ves[i-1].F,ves[i].F,ves[i-1].S,v.p);
			}
			add(ves.back().F,v.r,ves.back().S,v.p);
			for(auto u:ves){
				st.erase(u);
			}
			st.insert(mp(v.l,v.p));
			st.insert(mp(v.r,ves.back().S));
		}else{
			add(v.l,v.r,omghl.S,v.p);
			st.insert(mp(v.l,v.p));
			st.insert(mp(v.r,omghl.S));
		}
	}
	auto it=st.begin();
	while(it!=st.end()){
		auto itt=it;
		itt++;
		if(itt==st.end()){
			add((*it).F,inf,(*it).S,inf);
		}else{
			add((*it).F,(*itt).F,(*it).S,inf);
		}
		it=itt;
	}
}
ll answer[maxn];
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n,q,k;
	//cin>>n>>q>>k;
	n=readIntSp(1,3e5);
	q=readIntSp(1,3e5);
	k=readIntLn(1,n);
	vector<ll> comp;
	comp.pb(0);
	for(ll i=0;i<n;i++){
		Store E;
		//cin>>E.p>>E.d>>E.l>>E.r;
		E.p=readIntSp(1,1e9);
		E.d=readIntSp(1,k);
		E.l=readIntSp(1,1e9);
		E.r=readIntLn(E.l,1e9);
		E.r++;
		comp.pb(E.l);
		comp.pb(E.r);
		E.d--;
		a[E.d].pb(E);
	}
	for(ll i=0;i<k;i++){
		addImp(a[i]);
	}
	for(ll i=0;i<q;i++){
		ll x,t;
		//cin>>x>>t;
		x=readIntSp(1,1e9);
		t=readIntLn(1,1e9);
		Event a;
		a.x=x*2;
		a.l=t;
		a.c='?';
		a.r=i;
		Ev.pb(a);
	}
	sort(comp.begin(),comp.end());
	for(ll i=0;i<(ll)Ev.size();i++){
		if(Ev[i].c=='?'){
			Ev[i].l=upper_bound(comp.begin(),comp.end(),Ev[i].l)-comp.begin()-1;
		}else{
			Ev[i].l=lower_bound(comp.begin(),comp.end(),Ev[i].l)-comp.begin();
			Ev[i].r=lower_bound(comp.begin(),comp.end(),Ev[i].r)-comp.begin();
		}
	}
	for(ll i=0;i<(ll)firstt.size();i++){
		firstt[i].l=lower_bound(comp.begin(),comp.end(),firstt[i].l)-comp.begin();
		firstt[i].r=lower_bound(comp.begin(),comp.end(),firstt[i].r)-comp.begin();
	}
	sort(Ev.begin(),Ev.end(),cmpp);
	/*
	for(auto e:Ev){
		cout<<e.x<<":"<<e.l<<' '<<e.r<<"  #  "<<e.c<<endl;
	}
	for(auto e:firstt){
		cout<<e.x<<":"<<e.l<<' '<<e.r<<"  *  "<<e.c<<endl;
	}*/
	ll m=comp.size();
	W.bild();
	R.bild();
 
 
	R.updateC(0,m,1,0,m,-k);
	for(auto e:firstt){
		if(e.x>=inf){
			W.updateK(0,m,1,e.l,e.r,1);
		}else{
			R.updateK(0,m,1,e.l,e.r,e.x*2);
		}
	}
	ll lastt=0;
	for(auto e:Ev){
		if(lastt!=e.x){
			R.begzar(e.x-lastt);
			lastt=e.x;
		}
		if(e.c=='?'){
			if(W.findVal(0,m,1,e.l)==0){
				answer[e.r]=R.findVal(0,m,1,e.l);
			}else{
				answer[e.r]=-2;
			}
		}else{
			R.updateC(0,m,1,e.l,e.r,e.c);
		}
	}
	for(ll i=0;i<q;i++){
		cout<<answer[i]/2<<endl;
	}
}

Feel free to share your approach. As usual, suggestions are warmly welcomed. :slight_smile: