제출 #99805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99805		TadijaSebez	새 집 (APIO18_new_home)	C++11	5 / 100	5102 ms	365460 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
struct Compress
{
	vector<int> id;
	void Add(int x){ id.pb(x);}
	void Build(){ sort(id.begin(),id.end());id.erase(unique(id.begin(),id.end()),id.end());}
	int GetL(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;}
	int GetR(int x){ return upper_bound(id.begin(),id.end(),x)-id.begin();}
	int Val(int x){ return id[x-1];}
	int size(){ return id.size();}
} TME,LOC;
const int N=300050;
const int M=2*N;
const int K=2*M;
const int inf=1e9+7;
struct SegmentTree
{
	multiset<int> val[K];
	int ls[K],rs[K],tsz,root;
	string name;
	SegmentTree(){}
	void SetName(string s){ name=s;}
	void Add(int &c, int ss, int se, int qs, int qe, int f, int t)
	{
		if(qs>qe || qs>se || ss>qe) return;
		if(!c) c=++tsz;
		if(qs<=ss && qe>=se)
		{
			if(t==1) val[c].insert(f);
			else
			{
				//if(!val[c].count(f)) printf("???\n");
				val[c].erase(val[c].find(f));
			}
			return;
		}
		int mid=ss+se>>1;
		Add(ls[c],ss,mid,qs,qe,f,t);
		Add(rs[c],mid+1,se,qs,qe,f,t);
	}
	void Add(int qs, int qe, int f)
	{
		//cout<<name<<":Add: ("<<qs<<", "<<qe<<") "<<f<<"\n";
		Add(root,1,M,qs,qe,f,1);
	}
	void Del(int qs, int qe, int f)
	{
		//cout<<name<<":Del: ("<<qs<<", "<<qe<<") "<<f<<"\n";
		Add(root,1,M,qs,qe,f,0);
	}
	int Get(int c, int ss, int se, int qi)
	{
		int ans=val[c].size()?*val[c].rbegin():-inf;
		if(ss==se) return ans;
		int mid=ss+se>>1;
		if(qi<=mid) ans=max(ans,Get(ls[c],ss,mid,qi));
		else ans=max(ans,Get(rs[c],mid+1,se,qi));
		return ans;
	}
	int Get(int qi){ return Get(root,1,M,qi);}
} LST,RST;
int x[N],t[N],l[N],r[N],qx[N],qy[N],ans[N],k,active;
vector<int> QS[M],L[M],R[M];
set<pair<int,int>> all[N];
void Add(int i)
{
	all[t[i]].insert(mp(x[i],i));
	auto it=all[t[i]].find(mp(x[i],i));
	bool lf=0,rf=0;
	int lid,rid;
	if(it!=all[t[i]].begin()) it--,lid=it->second,lf=1,it++;
	it++;if(it!=all[t[i]].end()) rid=it->second,rf=1;it--;
	if(lf && rf)
	{
		int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
		LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));

		mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
		LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Add(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));

		mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
		LST.Add(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
		RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
	}
	else if(lf)
	{
		LST.Del(x[lid],LOC.size(),-LOC.Val(x[lid]));
		LST.Add(x[i],LOC.size(),-LOC.Val(x[i]));
		int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
		LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Add(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
	}
	else if(rf)
	{
		RST.Del(1,x[rid],LOC.Val(x[rid]));
		RST.Add(1,x[i],LOC.Val(x[i]));
		int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
		LST.Add(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
		RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
	}
	else
	{
		LST.Add(x[i],LOC.size(),-LOC.Val(x[i]));
		RST.Add(1,x[i],LOC.Val(x[i]));
	}
	if(all[t[i]].size()==1) active++;
}
void Del(int i)
{
	auto it=all[t[i]].find(mp(x[i],i));
	bool lf=0,rf=0;
	int lid,rid;
	if(it!=all[t[i]].begin()) it--,lid=it->second,lf=1,it++;
	it++;if(it!=all[t[i]].end()) rid=it->second,rf=1;it--;
	if(lf && rf)
	{
		int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
		LST.Add(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Add(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));

		mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
		LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Del(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));

		mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
		LST.Del(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
		RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
	}
	else if(lf)
	{
		LST.Add(x[lid],LOC.size(),-LOC.Val(x[lid]));
		LST.Del(x[i],LOC.size(),-LOC.Val(x[i]));
		int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
		LST.Del(x[lid],LOC.GetR(mid),-LOC.Val(x[lid]));
		RST.Del(LOC.GetL(mid+1),x[i],LOC.Val(x[i]));
	}
	else if(rf)
	{
		RST.Add(1,x[rid],LOC.Val(x[rid]));
		RST.Del(1,x[i],LOC.Val(x[i]));
		int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
		LST.Del(x[i],LOC.GetR(mid),-LOC.Val(x[i]));
		RST.Del(LOC.GetL(mid+1),x[rid],LOC.Val(x[rid]));
	}
	else
	{
		LST.Del(x[i],LOC.size(),-LOC.Val(x[i]));
		RST.Del(1,x[i],LOC.Val(x[i]));
	}
	if(all[t[i]].size()==1) active--;
	all[t[i]].erase(mp(x[i],i));
}
int Get(int i)
{
	if(active!=k) return -1;
	int ans=max(LST.Get(qx[i])+LOC.Val(qx[i]),RST.Get(qx[i])-LOC.Val(qx[i]));
	//printf("%i %i %i\n",LST.Get(qx[i])+LOC.Val(qx[i]),RST.Get(qx[i])-LOC.Val(qx[i]),ans);
	return ans;
}
void Solve(int ss, int se, vector<int> work)
{
	for(int i:work) L[l[i]].pb(i),R[r[i]].pb(i);
	for(int i=ss;i<=se;i++)
	{
		for(int j:L[i]) Add(j);
		for(int j:QS[i]) ans[j]=Get(j);
		for(int j:R[i]) Del(j);
	}
}
int main()
{
	LST.SetName("LST");
	RST.SetName("RST");
	int n,q;
	scanf("%i %i %i",&n,&k,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i %i %i",&x[i],&t[i],&l[i],&r[i]);
		TME.Add(l[i]);
		TME.Add(r[i]);
		LOC.Add(x[i]);
	}
	for(int i=1;i<=q;i++)
	{
		scanf("%i %i",&qx[i],&qy[i]);
		TME.Add(qy[i]);
		LOC.Add(qx[i]);
	}
	TME.Build();
	LOC.Build();
	for(int i=1;i<=n;i++)
	{
		l[i]=TME.GetL(l[i]);
		r[i]=TME.GetL(r[i]);
		x[i]=LOC.GetL(x[i]);
	}
	for(int i=1;i<=q;i++)
	{
		qy[i]=TME.GetL(qy[i]);
		qx[i]=LOC.GetL(qx[i]);
		QS[qy[i]].pb(i);
	}
	vector<int> work(n);
	for(int i=1;i<=n;i++) work[i-1]=i;
	Solve(1,TME.size(),work);
	for(int i=1;i<=q;i++) printf("%i\n",ans[i]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In member function 'void SegmentTree::Add(int&, int, int, int, int, int, int)':
new_home.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
new_home.cpp: In member function 'int SegmentTree::Get(int, int, int, int)':
new_home.cpp:58:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
new_home.cpp: In function 'void Add(int)':
new_home.cpp:78:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:82:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:86:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:94:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:102:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void Del(int)':
new_home.cpp:122:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[lid])+LOC.Val(x[rid])>>1;
           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:126:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:130:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp:138:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[lid])+LOC.Val(x[i])>>1;
           ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp:146:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=LOC.Val(x[i])+LOC.Val(x[rid])>>1;
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:180: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:183: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:190: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: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20