Submission #53259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53259	2018-06-29T06:04:26 Z	zetapi	New Home (APIO18_new_home)	C++14	10 / 100	4230 ms	1095252 KB

new_home

#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e7;
const int INF=1e8;
 
struct data
{
	int val;
	int left;
	int right;
}  	seg[MAX],seg_[MAX];

multiset<int> st[MAX];
multiset<int> itr it,nxt,pre;

vector<int> vec[MAX];

vector<pii> order;

vector< pair<int,pii> > ask;

int N,K,Q,X,Y,n,t,timer,timers,ptr,type[MAX],loc[MAX],res[MAX];
 
int get(int X,int Y)
{
	return Y-X;
}
 
int gets(int X,int Y)
{
	if(!Y)
		return 0;
	return X-Y;
}
 
void UpdateNeg(int low,int high,int node,int qlow,int delta)
{	
	if(low>high or qlow>high)
		return ;
	if(qlow<=low)
	{
		seg[node].val=max(seg[node].val,delta);
		return ;
	}
	if(!seg[node].left)
		seg[node].left=++timer;
	if(!seg[node].right)
		seg[node].right=++timer;
	int mid=(low+high)/2;
	UpdateNeg(low,mid,seg[node].left,qlow,delta);
	UpdateNeg(mid+1,high,seg[node].right,qlow,delta);
	return ;
}
 
void UpdatePos(int low,int high,int node,int qhigh,int delta)
{
	if(low>high or low>qhigh)
		return ;
	if(high<=qhigh)
	{
		if(!seg_[node].val)
			seg_[node].val=delta;
		else
			seg_[node].val=min(seg_[node].val,delta);
		return ;
	}
	if(!seg_[node].left)
		seg_[node].left=++timers;
	if(!seg_[node].right)
		seg_[node].right=++timers;
	int mid=(low+high)/2;
	UpdatePos(low,mid,seg_[node].left,qhigh,delta);
	UpdatePos(mid+1,high,seg_[node].right,qhigh,delta);
	return ;
}
 
int QueryNeg(int low,int high,int node,int idx)
{
	if(!node)
		return 0;
	if(low==high)
		return get(idx,seg[node].val);
	int mid=(low+high)/2;
	if(idx>=low and idx<=mid)
		return max(get(idx,seg[node].val),QueryNeg(low,mid,seg[node].left,idx));
	else
		return max(get(idx,seg[node].val),QueryNeg(mid+1,high,seg[node].right,idx));
}
 
int QueryPos(int low,int high,int node,int idx)
{
	if(!node)
		return 0;
	if(low==high)
		return gets(idx,seg_[node].val);
	int mid=(low+high)/2;
	if(idx>=low and idx<=mid)
		return max(gets(idx,seg_[node].val),QueryPos(low,mid,seg_[node].left,idx));
	else
		return max(gets(idx,seg_[node].val),QueryPos(mid+1,high,seg_[node].right,idx));
}
 
void exclude(int ind)
{
	int CurType=type[ind],CurLoc=loc[ind];
	it=st[CurType].find(CurLoc);
	if(it==st[CurType].begin() and (++it)==st[CurType].end())
	{
		UpdateNeg(1,n,1,1,INF);
		st[CurType].erase(--it);
		return ;
	}
	--it;
	if(it==st[CurType].begin())
	{
		nxt=it;
		++nxt;
		UpdateNeg(1,n,1,1,*nxt);
		st[CurType].erase(it);
	}
	else if((++it)==st[CurType].end())
	{
		--it;
		pre=it;
		--pre;
		UpdatePos(1,n,1,n,*pre);
		st[CurType].erase(it);
	}
	else
	{
		pre=it;
		nxt=it;
		--pre;
		++nxt;
		UpdatePos(1,n,1,(*pre+*nxt)/2,*pre);
		UpdateNeg(1,n,1,(*pre+*nxt+1)/2,*nxt);	
		st[CurType].erase(it);
	}
	return ;
}

signed main()
{
	ios_base::sync_with_stdio(false);
 
	n=INF;
	timer=1;
	timers=1;
	cin>>N>>K>>Q;
	for(int A=1;A<=N;A++)
	{
		cin>>loc[A]>>type[A]>>X>>X;
		vec[type[A]].pb(loc[A]);
		st[type[A]].insert(loc[A]);
		order.pb(mp(X,A));
	}
	sort(order.begin(),order.end());
	for(int A=1;A<=K;A++)
	{
		if(vec[A].empty())
		{
			while(Q--)
				cout<<-1<<"\n";
			return 0;
		}
		sort(vec[A].begin(),vec[A].end());
		for(int B=1;B<vec[A].size();B++)
			UpdateNeg(1,n,1,(vec[A][B]+vec[A][B-1]+1)/2,vec[A][B]);
		for(int B=0;B<vec[A].size()-1;B++)
			UpdatePos(1,n,1,(vec[A][B]+vec[A][B+1])/2,vec[A][B]);
		UpdateNeg(1,n,1,1,*vec[A].begin());
		UpdatePos(1,n,1,n,vec[A].back());
	}
	for(int A=1;A<=Q;A++)
	{
		cin>>X>>Y;
		ask.pb(mp(Y,mp(X,A)));
	}
	sort(ask.begin(),ask.end());
	for(auto A:ask)
	{
		while(ptr<order.size() and order[ptr].first<A.first)
		{
			exclude(order[ptr].second);
			++ptr;
		}
		res[A.second.second]=max(QueryPos(1,n,1,A.second.first),QueryNeg(1,n,1,A.second.first));
	}
	for(int A=1;A<=Q;A++)
	{
		if(res[A]==INF)
			res[A]=-1;
		cout<<res[A]<<"\n";
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:175:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=0;B<vec[A].size()-1;B++)
               ~^~~~~~~~~~~~~~~~
new_home.cpp:190:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<order.size() and order[ptr].first<A.first)
         ~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	577 ms	704900 KB	Output is correct
2	Incorrect	579 ms	705024 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	577 ms	704900 KB	Output is correct
2	Incorrect	579 ms	705024 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2447 ms	928312 KB	Output is correct
2	Correct	2536 ms	965312 KB	Output is correct
3	Correct	1210 ms	965312 KB	Output is correct
4	Correct	2287 ms	965312 KB	Output is correct
5	Correct	2393 ms	975576 KB	Output is correct
6	Correct	2442 ms	975576 KB	Output is correct
7	Correct	1000 ms	975576 KB	Output is correct
8	Correct	2370 ms	975576 KB	Output is correct
9	Correct	2776 ms	975576 KB	Output is correct
10	Correct	2475 ms	975576 KB	Output is correct
11	Correct	1812 ms	975576 KB	Output is correct
12	Correct	2261 ms	975576 KB	Output is correct