Submission #99893

#	Time	Username	Problem	Language	Result	Execution time	Memory
99893		TadijaSebez	New Home (APIO18_new_home)	C++11	47 / 100	5143 ms	616112 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mt make_tuple
const int N=300050;
const int M=4*N;
const int lim=1e8;
int x[N],t[N],l[N],r[N],qx[N],qy[N],active,ans[N];
set<pair<int,int>> all[N];
map<pair<int,int>,int> T[N];
vector<tuple<int,int,int,int>> L,R;
void Put(int t, int l, int r, int ins, int tme)
{
	int mid=l+r>>1;
	if(l>r) return;
	if(ins==0)
	{
		if(l!=-2*lim) T[t][mp(l,mid)]=tme;
		if(r!=2*lim) T[t][mp(mid+1,r)]=tme;
	}
	else
	{
		if(l!=-2*lim) L.pb(mt(T[t][mp(l,mid)],tme-1,l,mid));
		if(r!=2*lim) R.pb(mt(T[t][mp(mid+1,r)],tme-1,mid+1,r));
	}
}
int root,ls[M],rs[M],tsz;
vector<pair<int,int>> LST,RST;
vector<pair<pair<int,int>,int>> STL[M],STR[M];
/*void AddL(int &c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ LST[c].pb(mp(l,r));return;}
	int mid=ss+se>>1;
	AddL(ls[c],ss,mid,qs,qe,l,r);
	AddL(rs[c],mid+1,se,qs,qe,l,r);
}
void AddR(int &c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ RST[c].pb(mp(l,r));return;}
	int mid=ss+se>>1;
	AddR(ls[c],ss,mid,qs,qe,l,r);
	AddR(rs[c],mid+1,se,qs,qe,l,r);
}*/
int lsz[M],rsz[M];
void Build(int &c, int ss, int se, vector<int> l, vector<int> r)
{
	c=++tsz;int mid=ss+se>>1;
	vector<int> PLL,PRL,PLR,PRR;
	LST.clear();RST.clear();
	for(int j=0;j<l.size();j++)
	{
		int i=l[j];
		if(get<0>(L[i])<=ss && get<1>(L[i])>=se) LST.pb(mp(get<2>(L[i]),get<3>(L[i])));
		else
		{
			if(get<0>(L[i])<=mid) PLL.pb(i);
			if(get<1>(L[i])>mid) PRL.pb(i);
		}
	}
	for(int j=0;j<r.size();j++)
	{
		int i=r[j];
		if(get<0>(R[i])<=ss && get<1>(R[i])>=se) RST.pb(mp(get<2>(R[i]),get<3>(R[i])));
		else
		{
			if(get<0>(R[i])<=mid) PLR.pb(i);
			if(get<1>(R[i])>mid) PRR.pb(i);
		}
	}
	STL[c].reserve(LST.size());
	int mx=-lim;
	for(int i=0;i<LST.size();i++)
	{
		if(LST[i].second>=mx)
		{
			STL[c].pb(mp(mp(max(LST[i].first,mx),LST[i].second),LST[i].first));
			mx=LST[i].second+1;
			//printf("%i %i %i\n",get<0>(STL[c].back()),get<1>(STL[c].back()),get<2>(STL[c].back()));
		}
	}
	lsz[c]=STL[c].size();
	STR[c].reserve(RST.size());
	int mn=lim*2;
	for(int i=0;i<RST.size();i++)
	{
		if(RST[i].first<=mn)
		{
			STR[c].pb(mp(mp(RST[i].first,min(RST[i].second,mn)),RST[i].second));
			mn=RST[i].first-1;
			//printf("%i %i %i\n",get<0>(STR[c].back()),get<1>(STR[c].back()),get<2>(STR[c].back()));
		}
	}
	reverse(STR[c].begin(),STR[c].end());
	rsz[c]=STR[c].size();
	LST.clear();RST.clear();R.clear();L.clear();
	if(ss==se) return;
	Build(ls[c],ss,mid,PLL,PLR);
	PLL.clear();PLR.clear();
	Build(rs[c],mid+1,se,PRL,PRR);
	PRL.clear();PRR.clear();
}
int Solve(int c, int ss, int se, int qi, int x)
{
	int ans=0;
	while(lsz[c] && STL[c][lsz[c]-1].first.first>x) lsz[c]--;
	while(rsz[c] && STR[c][rsz[c]-1].first.first>x)	rsz[c]--;
	if(lsz[c] && STL[c][lsz[c]-1].first.second>=x) ans=max(ans,x-STL[c][lsz[c]-1].second);
	if(rsz[c] && STR[c][rsz[c]-1].first.second>=x) ans=max(ans,STR[c][rsz[c]-1].second-x);
	if(ss==se) return ans;
	int mid=ss+se>>1;
	if(qi<=mid) return max(ans,Solve(ls[c],ss,mid,qi,x));
	else return max(ans,Solve(rs[c],mid+1,se,qi,x));
}
int main()
{
	int n,k,q,i;
	scanf("%i %i %i",&n,&k,&q);
	vector<tuple<int,int,int>> events;
	for(i=1;i<=n;i++)
	{
		scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
		events.pb(mt(l[i],0,i));
		events.pb(mt(r[i]+1,1,i));
	}
	for(i=1;i<=q;i++)
	{
		scanf("%i %i",&qx[i],&qy[i]);
		events.pb(mt(qy[i],2,i));
	}
	for(i=1;i<=k;i++)
	{
		all[i].insert(mp(-2*lim,-1));
		all[i].insert(mp(2*lim,0));
		Put(i,-2*lim,2*lim,0,2*lim);
	}
	sort(events.begin(),events.end());
	vector<int> work;
	for(auto e:events)
	{
		int tme=get<0>(e);
		int type=get<1>(e);
		int i=get<2>(e);
		if(type!=2)
		{
			if(type==0) all[t[i]].insert(mp(x[i],i));
			auto it=all[t[i]].find(mp(x[i],i));
			int lid=0,rid=0;
			if(it!=all[t[i]].begin()) it--,lid=it->first,it++;
			it++;if(it!=all[t[i]].end()) rid=it->first;it--;
			if(type==0) Put(t[i],lid,rid,type^1,tme);
			Put(t[i],lid,x[i],type,tme);
			Put(t[i],x[i],rid,type,tme);
			if(type==1) Put(t[i],lid,rid,type^1,tme);
			if(all[t[i]].size()==3) active+=type==0?1:-1;
			if(type==1) all[t[i]].erase(mp(x[i],i));
		}
		else
		{
			if(active!=k) ans[i]=-1;
			else work.pb(i);
		}
		//printf("%i %i %i %i\n",tme,type,i,active);
	}
	sort(L.begin(),L.end(),[](tuple<int,int,int,int> a, tuple<int,int,int,int> b){ return get<2>(a)<get<2>(b);});
	sort(R.begin(),R.end(),[](tuple<int,int,int,int> a, tuple<int,int,int,int> b){ return get<3>(a)>get<3>(b);});
	sort(work.begin(),work.end(),[&](int a, int b){ return qx[a]>qx[b];});
	vector<int> id;
	for(auto tp:L) id.pb(get<0>(tp)),id.pb(get<1>(tp));
	for(auto tp:R) id.pb(get<0>(tp)),id.pb(get<1>(tp));
	for(int idx:work) id.pb(qy[idx]);
	sort(id.begin(),id.end());
	id.erase(unique(id.begin(),id.end()),id.end());
	auto Get=[&](int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;};
	for(auto &tp:L) tp=mt(Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	for(auto &tp:R) tp=mt(Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	//for(auto tp:L) AddL(root,1,id.size(),Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	//for(auto tp:R) AddR(root,1,id.size(),Get(get<0>(tp)),Get(get<1>(tp)),get<2>(tp),get<3>(tp));
	vector<int> lb,rb;
	for(int i=0;i<L.size();i++) lb.pb(i);
	for(int i=0;i<R.size();i++) rb.pb(i);
	Build(root,1,id.size(),lb,rb);
	for(int idx:work) ans[idx]=Solve(root,1,id.size(),Get(qy[idx]),qx[idx]);
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void Put(int, int, int, int, int)':
new_home.cpp:15:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
new_home.cpp: In function 'void Build(int&, int, int, std::vector<int>, std::vector<int>)':
new_home.cpp:52:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  c=++tsz;int mid=ss+se>>1;
                  ~~^~~
new_home.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<l.size();j++)
              ~^~~~~~~~~
new_home.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<r.size();j++)
              ~^~~~~~~~~
new_home.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<LST.size();i++)
              ~^~~~~~~~~~~
new_home.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<RST.size();i++)
              ~^~~~~~~~~~~
new_home.cpp: In function 'int Solve(int, int, int, int, int)':
new_home.cpp:115:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:184:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L.size();i++) lb.pb(i);
              ~^~~~~~~~~
new_home.cpp:185:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<R.size();i++) rb.pb(i);
              ~^~~~~~~~~
new_home.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&qx[i],&qy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20