oj.uz

Submission #53236

# Submission time Handle Problem Language Result Execution time Memory
53236 2018-06-29T05:05:51 Z zetapi New Home (APIO18_new_home) C++14
0 / 100
 2451 ms 350444 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=5e6;
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 get(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 110 ms 117836 KB Output is correct
2 Incorrect 105 ms 117992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 117836 KB Output is correct
2 Incorrect 105 ms 117992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2339 ms 301404 KB Output is correct
2 Incorrect 2162 ms 350444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2451 ms 350444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 117836 KB Output is correct
2 Incorrect 105 ms 117992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 117836 KB Output is correct
2 Incorrect 105 ms 117992 KB Output isn't correct
3 Halted 0 ms 0 KB -