oj.uz

Submission #99805

# Submission time Handle Problem Language Result Execution time Memory
99805 2019-03-07T13:13:09 Z TadijaSebez New Home (APIO18_new_home) C++11
5 / 100
 5000 ms 365460 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 169420 KB Output is correct
2 Correct 167 ms 169492 KB Output is correct
3 Correct 162 ms 169436 KB Output is correct
4 Correct 166 ms 169464 KB Output is correct
5 Correct 169 ms 169628 KB Output is correct
6 Correct 160 ms 169736 KB Output is correct
7 Correct 157 ms 169664 KB Output is correct
8 Correct 161 ms 169804 KB Output is correct
9 Correct 159 ms 169848 KB Output is correct
10 Correct 172 ms 169720 KB Output is correct
11 Correct 181 ms 169692 KB Output is correct
12 Correct 159 ms 169552 KB Output is correct
13 Correct 161 ms 169632 KB Output is correct
14 Correct 175 ms 169564 KB Output is correct
15 Correct 163 ms 169720 KB Output is correct
16 Correct 157 ms 169768 KB Output is correct
17 Correct 157 ms 169592 KB Output is correct
18 Correct 160 ms 169720 KB Output is correct
19 Correct 163 ms 169848 KB Output is correct
20 Correct 171 ms 169860 KB Output is correct
21 Correct 158 ms 169672 KB Output is correct
22 Correct 169 ms 169964 KB Output is correct
23 Correct 158 ms 169848 KB Output is correct
24 Correct 158 ms 169720 KB Output is correct
25 Correct 159 ms 169676 KB Output is correct
26 Correct 159 ms 169628 KB Output is correct
27 Correct 174 ms 169592 KB Output is correct
28 Correct 178 ms 169592 KB Output is correct
29 Correct 165 ms 169556 KB Output is correct
30 Correct 166 ms 169644 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 169420 KB Output is correct
2 Correct 167 ms 169492 KB Output is correct
3 Correct 162 ms 169436 KB Output is correct
4 Correct 166 ms 169464 KB Output is correct
5 Correct 169 ms 169628 KB Output is correct
6 Correct 160 ms 169736 KB Output is correct
7 Correct 157 ms 169664 KB Output is correct
8 Correct 161 ms 169804 KB Output is correct
9 Correct 159 ms 169848 KB Output is correct
10 Correct 172 ms 169720 KB Output is correct
11 Correct 181 ms 169692 KB Output is correct
12 Correct 159 ms 169552 KB Output is correct
13 Correct 161 ms 169632 KB Output is correct
14 Correct 175 ms 169564 KB Output is correct
15 Correct 163 ms 169720 KB Output is correct
16 Correct 157 ms 169768 KB Output is correct
17 Correct 157 ms 169592 KB Output is correct
18 Correct 160 ms 169720 KB Output is correct
19 Correct 163 ms 169848 KB Output is correct
20 Correct 171 ms 169860 KB Output is correct
21 Correct 158 ms 169672 KB Output is correct
22 Correct 169 ms 169964 KB Output is correct
23 Correct 158 ms 169848 KB Output is correct
24 Correct 158 ms 169720 KB Output is correct
25 Correct 159 ms 169676 KB Output is correct
26 Correct 159 ms 169628 KB Output is correct
27 Correct 174 ms 169592 KB Output is correct
28 Correct 178 ms 169592 KB Output is correct
29 Correct 165 ms 169556 KB Output is correct
30 Correct 166 ms 169644 KB Output is correct
31 Execution timed out 5022 ms 231528 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 365460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5081 ms 322740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 169420 KB Output is correct
2 Correct 167 ms 169492 KB Output is correct
3 Correct 162 ms 169436 KB Output is correct
4 Correct 166 ms 169464 KB Output is correct
5 Correct 169 ms 169628 KB Output is correct
6 Correct 160 ms 169736 KB Output is correct
7 Correct 157 ms 169664 KB Output is correct
8 Correct 161 ms 169804 KB Output is correct
9 Correct 159 ms 169848 KB Output is correct
10 Correct 172 ms 169720 KB Output is correct
11 Correct 181 ms 169692 KB Output is correct
12 Correct 159 ms 169552 KB Output is correct
13 Correct 161 ms 169632 KB Output is correct
14 Correct 175 ms 169564 KB Output is correct
15 Correct 163 ms 169720 KB Output is correct
16 Correct 157 ms 169768 KB Output is correct
17 Correct 157 ms 169592 KB Output is correct
18 Correct 160 ms 169720 KB Output is correct
19 Correct 163 ms 169848 KB Output is correct
20 Correct 171 ms 169860 KB Output is correct
21 Correct 158 ms 169672 KB Output is correct
22 Correct 169 ms 169964 KB Output is correct
23 Correct 158 ms 169848 KB Output is correct
24 Correct 158 ms 169720 KB Output is correct
25 Correct 159 ms 169676 KB Output is correct
26 Correct 159 ms 169628 KB Output is correct
27 Correct 174 ms 169592 KB Output is correct
28 Correct 178 ms 169592 KB Output is correct
29 Correct 165 ms 169556 KB Output is correct
30 Correct 166 ms 169644 KB Output is correct
31 Execution timed out 5022 ms 231528 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 169420 KB Output is correct
2 Correct 167 ms 169492 KB Output is correct
3 Correct 162 ms 169436 KB Output is correct
4 Correct 166 ms 169464 KB Output is correct
5 Correct 169 ms 169628 KB Output is correct
6 Correct 160 ms 169736 KB Output is correct
7 Correct 157 ms 169664 KB Output is correct
8 Correct 161 ms 169804 KB Output is correct
9 Correct 159 ms 169848 KB Output is correct
10 Correct 172 ms 169720 KB Output is correct
11 Correct 181 ms 169692 KB Output is correct
12 Correct 159 ms 169552 KB Output is correct
13 Correct 161 ms 169632 KB Output is correct
14 Correct 175 ms 169564 KB Output is correct
15 Correct 163 ms 169720 KB Output is correct
16 Correct 157 ms 169768 KB Output is correct
17 Correct 157 ms 169592 KB Output is correct
18 Correct 160 ms 169720 KB Output is correct
19 Correct 163 ms 169848 KB Output is correct
20 Correct 171 ms 169860 KB Output is correct
21 Correct 158 ms 169672 KB Output is correct
22 Correct 169 ms 169964 KB Output is correct
23 Correct 158 ms 169848 KB Output is correct
24 Correct 158 ms 169720 KB Output is correct
25 Correct 159 ms 169676 KB Output is correct
26 Correct 159 ms 169628 KB Output is correct
27 Correct 174 ms 169592 KB Output is correct
28 Correct 178 ms 169592 KB Output is correct
29 Correct 165 ms 169556 KB Output is correct
30 Correct 166 ms 169644 KB Output is correct
31 Execution timed out 5022 ms 231528 KB Time limit exceeded
32 Halted 0 ms 0 KB -