oj.uz

Submission #53275

# Submission time Handle Problem Language Result Execution time Memory
53275 2018-06-29T06:41:32 Z zetapi New Home (APIO18_new_home) C++14
33 / 100
 4395 ms 1179648 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,ok,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())
	{
	 	if((++it)==st[CurType].end())
		{
			ok=1;
			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
	{
      	--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+9;
	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,INF,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;
		}
		if(ok)
			res[A.second.second]=-1;
		else
			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++)
		cout<<res[A]<<"\n";
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:179:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:181:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=0;B<vec[A].size()-1;B++)
               ~^~~~~~~~~~~~~~~~
new_home.cpp:194: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 576 ms 704780 KB Output is correct
2 Correct 575 ms 704872 KB Output is correct
3 Correct 608 ms 704992 KB Output is correct
4 Incorrect 619 ms 705164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 704780 KB Output is correct
2 Correct 575 ms 704872 KB Output is correct
3 Correct 608 ms 704992 KB Output is correct
4 Incorrect 619 ms 705164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2592 ms 928596 KB Output is correct
2 Correct 2535 ms 965480 KB Output is correct
3 Correct 1271 ms 965480 KB Output is correct
4 Correct 2525 ms 965480 KB Output is correct
5 Correct 2425 ms 975712 KB Output is correct
6 Correct 2656 ms 975712 KB Output is correct
7 Correct 1040 ms 975712 KB Output is correct
8 Correct 2302 ms 975712 KB Output is correct
9 Correct 2481 ms 975712 KB Output is correct
10 Correct 2622 ms 975712 KB Output is correct
11 Correct 1907 ms 975712 KB Output is correct
12 Correct 2086 ms 975712 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4183 ms 1095452 KB Output is correct
2 Correct 1430 ms 1095452 KB Output is correct
3 Correct 4395 ms 1138092 KB Output is correct
4 Correct 1325 ms 1138092 KB Output is correct
5 Correct 2344 ms 1138092 KB Output is correct
6 Correct 2023 ms 1138092 KB Output is correct
7 Correct 4314 ms 1179648 KB Output is correct
8 Correct 4352 ms 1179648 KB Output is correct
9 Correct 1179 ms 1179648 KB Output is correct
10 Correct 2692 ms 1179648 KB Output is correct
11 Correct 3904 ms 1179648 KB Output is correct
12 Correct 4341 ms 1179648 KB Output is correct
13 Correct 2254 ms 1179648 KB Output is correct
14 Correct 2175 ms 1179648 KB Output is correct
15 Correct 2578 ms 1179648 KB Output is correct
16 Correct 2698 ms 1179648 KB Output is correct
17 Correct 2544 ms 1179648 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 704780 KB Output is correct
2 Correct 575 ms 704872 KB Output is correct
3 Correct 608 ms 704992 KB Output is correct
4 Incorrect 619 ms 705164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 704780 KB Output is correct
2 Correct 575 ms 704872 KB Output is correct
3 Correct 608 ms 704992 KB Output is correct
4 Incorrect 619 ms 705164 KB Output isn't correct
5 Halted 0 ms 0 KB -