Submission #53241

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53241	2018-06-29T05:11:25 Z	zetapi	New Home (APIO18_new_home)	C++14	10 / 100	2421 ms	586172 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];

vector<int> vec[MAX];

int N,K,Q,X,Y,n,type,loc,timer,timers;

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 ;
	//cout<<low<<" "<<high<<" "<<qlow<<" "<<delta<<"\n";
	if(qlow<=low)
	{
		//cout<<low<<" fuck "<<high<<" "<<node<<" "<<qlow<<" "<<delta<<"\n";
		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)
{
	//cout<<"low "<<low<<" high "<<high<<" "<<" node "<<node<<" "<<seg[node].val<<"\n";
	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));
}

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>>type>>X>>X;
		vec[type].pb(loc);
	}
	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++)
		{
			//cout<<(vec[A][B]+vec[A][B+1])/2<<" "<<vec[A][B]<<"\n";
			UpdatePos(1,n,1,(vec[A][B]+vec[A][B+1])/2,vec[A][B]);
		}
		//cout<<"ho ho "<<*vec[A].begin()<<"\n";
		UpdateNeg(1,n,1,1,*vec[A].begin());
		UpdatePos(1,n,1,n,vec[A].back());
	}
	//cout<<QueryNeg(1,n,1,1)<<"\n";
	/*UpdateNeg(1,10,1,3,6);
	UpdateNeg(1,10,1,4,5);
	UpdateNeg(1,10,1,1,2);*/
	while(Q--)
	{
		cin>>X>>Y;
		cout<<max(QueryPos(1,n,1,X),QueryNeg(1,n,1,X))<<"\n";
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=1;B<vec[A].size();B++)
               ~^~~~~~~~~~~~~~
new_home.cpp:133:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int B=0;B<vec[A].size()-1;B++)
               ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	235256 KB	Output is correct
2	Incorrect	214 ms	235256 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	235256 KB	Output is correct
2	Incorrect	214 ms	235256 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	2172 ms	418944 KB	Output is correct
2	Correct	2112 ms	455496 KB	Output is correct
3	Correct	978 ms	455496 KB	Output is correct
4	Correct	2064 ms	455496 KB	Output is correct
5	Correct	2230 ms	505204 KB	Output is correct
6	Correct	2177 ms	509752 KB	Output is correct
7	Correct	916 ms	509752 KB	Output is correct
8	Correct	2421 ms	509752 KB	Output is correct
9	Correct	2345 ms	530688 KB	Output is correct
10	Correct	2391 ms	561852 KB	Output is correct
11	Correct	1697 ms	570368 KB	Output is correct
12	Correct	1847 ms	586172 KB	Output is correct