oj.uz

Submission #137859

# Submission time Handle Problem Language Result Execution time Memory
137859 2019-07-28T12:47:55 Z mahmoudbadawy New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 365432 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 89592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 89592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2131 ms 300348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3071 ms 365432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 89592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 89592 KB Time limit exceeded
2 Halted 0 ms 0 KB -