oj.uz

Submission #1043358

# Submission time Handle Problem Language Result Execution time Memory
1043358 2024-08-04T08:46:39 Z vjudge1 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 188876 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,k,q;
	cin>>n>>k>>q;
	set<int> se;
	map<int,int> com;
	vector<vector<int>> ev,que;
	int t,a,s,e;
	for (int i=0;i<n;i++)
	{
		cin>>a>>t>>s>>e,t--;
		ev.push_back({s,e,a,t});
		se.insert(s),se.insert(t),se.insert(a);
	}
	int ans[q]={};
	while (q--)
	{
		int l,y;
		cin>>l>>y;
		se.insert(y);
		que.push_back({y,l,(int)que.size()});
	}
	for (int i:se)
		com[i]=com.size();
	int m=com.size();
	vector<pair<int,int>> st[m],en[m],qu[m];
	for (auto i:ev)
	{
		st[com[i[0]]].push_back({i[2],com[i[3]]});
		en[com[i[1]]].push_back({i[2],com[i[3]]});
	}
	for (auto i:que)
		qu[com[i[0]]].push_back({i[1],com[i[2]]});
	multiset<int> ms[k];
	for (int c=0;c<m;c++)
	{
		for (auto i:st[c])
			ms[i.second].insert(i.first);
		for (auto i:qu[c])
			for (t=0;t<k;t++)
			{
				if (ms[t].empty())
				{
					ans[i.second]=-1;
					break;
				}
				auto x=ms[t].lower_bound(i.first);
				int val=inf;
				if (x!=ms[t].end())
					val=*x-i.first;
				if (x!=ms[t].begin())
				{
					x--;
					val=min(val,i.first-*x);
				}
				ans[i.second]=max(ans[i.second],val);
			}
		for (auto i:en[c])
			ms[i.second].erase(ms[i.second].find(i.first));
	}
	for (int i:ans)
		cout<<i<<' ';
	cout<<endl;
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 5092 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 5092 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 5092 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 5092 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -