oj.uz

Submission #53268

# Submission time Handle Problem Language Result Execution time Memory
53268 2018-06-29T06:23:38 Z zetapi New Home (APIO18_new_home) C++14
10 / 100
 5000 ms 975672 KB 
#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].end())     
    {
		while(true)
    	it++;
	}
	if(it==st[CurType].begin() and (++it)==st[CurType].end())
	{
		UpdateNeg(1,n,1,1,INF+99);
		st[CurType].erase(--it);
		return ;
	}
	if(it==st[CurType].begin())
		--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
	{
      	--it;
		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:182:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:184:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=0;B<vec[A].size()-1;B++)
               ~^~~~~~~~~~~~~~~~
new_home.cpp:197: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 602 ms 704904 KB Output is correct
2 Correct 627 ms 705128 KB Output is correct
3 Correct 569 ms 705128 KB Output is correct
4 Execution timed out 5134 ms 705236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 704904 KB Output is correct
2 Correct 627 ms 705128 KB Output is correct
3 Correct 569 ms 705128 KB Output is correct
4 Execution timed out 5134 ms 705236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2396 ms 928432 KB Output is correct
2 Correct 2373 ms 965440 KB Output is correct
3 Correct 1215 ms 965440 KB Output is correct
4 Correct 2571 ms 965440 KB Output is correct
5 Correct 2437 ms 975672 KB Output is correct
6 Correct 2559 ms 975672 KB Output is correct
7 Correct 1049 ms 975672 KB Output is correct
8 Correct 2215 ms 975672 KB Output is correct
9 Correct 2457 ms 975672 KB Output is correct
10 Correct 2443 ms 975672 KB Output is correct
11 Correct 1805 ms 975672 KB Output is correct
12 Correct 2027 ms 975672 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 704904 KB Output is correct
2 Correct 627 ms 705128 KB Output is correct
3 Correct 569 ms 705128 KB Output is correct
4 Execution timed out 5134 ms 705236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 704904 KB Output is correct
2 Correct 627 ms 705128 KB Output is correct
3 Correct 569 ms 705128 KB Output is correct
4 Execution timed out 5134 ms 705236 KB Time limit exceeded
5 Halted 0 ms 0 KB -