Submission #134994

#	Time	Username	Problem	Language	Result	Execution time	Memory
134994		Lawliet	New Home (APIO18_new_home)	C++14	12 / 100	3284 ms	43216 KiB

new_home

#include <bits/stdc++.h>

#define MAXK 410
#define MAX 60010
#define INF 1000000000
#define L first.first
#define R first.second
#define X second.first
#define T second.second

using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> store;

struct query
{
	int x, year;
	int ind;

	query(int xx, int yy, int ii)
	{
		x = xx; year = yy;
		ind = ii;
	}

	bool operator < (const query& a)
	{
		if(year != a.year) return year < a.year;
		return ind < a.ind;
	}
};

int n, q, k;
int n1, n2, n3, n4;

int ans[MAX];

vector<query> queries;

vector<store> s;

multiset<int>::iterator it;

multiset<int> activedStoresType[MAXK];

multiset<pii> activedStores;

int main()
{
	scanf("%d %d %d",&n,&k,&q);

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d %d %d",&n1,&n2,&n3,&n4);

		s.push_back({{n3 , n4} , {n1 , n2}});
	}

	sort(s.begin() , s.end());

	for(int g = 1 ; g <= q ; g++)
	{
		scanf("%d %d",&n1,&n2);

		query k(n1 , n2 , g);

		queries.push_back( k );
	}

	sort(queries.begin() , queries.end());

	int nextStore = 0;

	for(int g = 0 ; g < q ; g++)
	{
		int x = queries[g].x;
		int year = queries[g].year;

		//printf("--------------------------------- %d %d\n",x,year);

		while(nextStore < n && s[nextStore].L <= year)//ATIVANDO OS CARINHAS
		{
			activedStores.insert({s[nextStore].R , nextStore});

			//printf("COLOQUEI type = %d   %d\n",s[nextStore].T,s[nextStore].X);

			activedStoresType[ s[nextStore].T ].insert( s[nextStore].X );

			nextStore++;
		}

		while(!activedStores.empty())
		{
			int cur = activedStores.begin()->second;

			//printf("oiii %d\n",s[cur].R);
			//printf("year = %d\n",year);

			if(year <= s[ cur ].R) break;

			activedStores.erase( activedStores.begin() );

			//printf("TIREI type = %d   %d\n",s[cur].T,s[cur].X);

			it = activedStoresType[ s[cur].T ].lower_bound( s[cur].X );

			activedStoresType[ s[cur].T ].erase( it );
		}

		int curAns = -1;

		bool typeEmpty = false;

		for(int t = 1 ; t <= k && !typeEmpty ; t++)
		{
			if(activedStoresType[t].empty())
			{
				typeEmpty = true;
				continue;
			}

			int cur = INF;

			it = activedStoresType[ t ].lower_bound( x );

			if(it != activedStoresType[ t ].end())
				cur = min(cur , abs(*it - x));

			if(it != activedStoresType[ t ].begin())
			{
				it--;

				cur = min(cur , abs(*it - x));
			}

			curAns = max(curAns , cur);
		}

		if(typeEmpty) ans[ queries[g].ind ] = -1;
		else ans[ queries[g].ind ] = curAns;
	}

	for(int g = 1 ; g <= q ; g++)
		printf("%d\n",ans[g]);
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&k,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&n1,&n2,&n3,&n4);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20