제출 #137862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137862		mahmoudbadawy	새 집 (APIO18_new_home)	C++17	0 / 100	5097 ms	352408 KiB

new_home

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

multiset<int> z[4*100005];
multiset<int> curmin,curmax;
vector< pair<int,int> > s[1000002],e[1000002];
pair< pair<int,int> , pair<int,int> > arr[3*100005];
pair< int,int > qs[3*100005];
int ans[3*100005];
vector< pair<int,int> > qy[10*100005];
set<int> ss;
map<int,int> m;
int n,q,k;

void add(int x,int y)
{
	if(z[x].size())
	{
		int lasmin=*(z[x].begin());
		int lasmax=*(--z[x].end());
		curmin.erase(curmin.find(lasmin));
		curmax.erase(curmax.find(-lasmax));
	}
	z[x].insert(y);
	int mini=*(z[x].begin());
	int maxi=*(--z[x].end());
	curmin.insert(mini);
	curmax.insert(-maxi);
}

void rem(int x,int y)
{
	int lasmin=*(z[x].begin());
	int lasmax=*(--z[x].end());
	curmin.erase(curmin.find(lasmin));
	curmax.erase(curmax.find(-lasmax));
	z[x].erase(z[x].find(y));
	if(z[x].size())
	{
		int mini=*(z[x].begin());
		int maxi=*(--z[x].end());
		curmin.insert(mini);
		curmax.insert(-maxi);
	}
}

int main()
{
	cin >> n >> k >> q;
	int yid=1;
	for(int i=0;i<n;i++)
	{
		// x t a b
		cin >> arr[i].F.F >> arr[i].F.S >> arr[i].S.F >> arr[i].S.S;
		arr[i].F.S--;
		ss.insert(arr[i].S.F); ss.insert(arr[i].S.S);
	}
	for(int i=0;i<q;i++)
	{
		// l y
		cin >> qs[i].F >> qs[i].S;
		ss.insert(qs[i].S);
	}
	for(auto it=ss.begin();it!=ss.end();it++)
	{
		m[*it]=yid++;
	}
	for(int i=0;i<n;i++)
	{
		s[m[arr[i].S.F]].push_back({arr[i].F.F,arr[i].F.S});
		e[m[arr[i].S.S]+1].push_back({arr[i].F.F,arr[i].F.S});
	}
	for(int i=0;i<q;i++)
	{
		qy[m[qs[i].S]].push_back({i,qs[i].F});
	}
	for(int i=0;i<k;i++)
		z[i].insert(-1);
	for(int i=1;i<yid;i++)
	{
		for(int j=0;j<s[i].size();j++)
			add(s[i][j].F,s[i][j].S);
		for(int j=0;j<e[i].size();j++)
			rem(e[i][j].F,e[i][j].S);
		int mini=(*curmin.begin()),maxi=-(*curmax.begin());
		int isneg=(-(*(--curmax.end()))==-1);
		for(int j=0;j<qy[i].size();j++)
		{
			ans[qy[i][j].F]=max(abs(maxi-qy[i][j].F),abs(mini-qy[i][j].F));
			if(isneg) ans[qy[i][j].F]=-1;
		}
	}
	for(int i=0;i<q;i++)
		cout << ans[i] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'int main()':
new_home.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<s[i].size();j++)
               ~^~~~~~~~~~~~
new_home.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<e[i].size();j++)
               ~^~~~~~~~~~~~
new_home.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<qy[i].size();j++)
               ~^~~~~~~~~~~~~

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