Submission #977199

#	Time	Username	Problem	Language	Result	Execution time	Memory
977199		vjudge1	New Home (APIO18_new_home)	C++17	10 / 100	302 ms	58928 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first

signed main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t1,t2,t3,t4;
	int n,k,q;cin>>n>>k>>q;
	
	priority_queue<pii,vector<pii>,greater<pii>>nummy;
	deque<pii>currpick;
	vector<priority_queue<int,vector<int>,greater<int>>>bytypes(k + 1);
	vector<int>tbp(k+1,0);
	//fill(tbp.begin(),tbp.end(),0);
	
	for (int a=0; a<n; a++)
	{
		cin >> t1 >> t2 >> t3 >> t4;
		nummy.push({t1,t2});
		bytypes[t2].push(t1);
	}
	//cerr << "yay you made it past one!:)\n";
	
	int currhav = 0;
	vector<bool>tracker(k+1,0);
	
	while ((!nummy.empty()) && currhav < k)
	{
		int currtype = nummy.top().second, currpos = nummy.top().first;
		if (tracker[currtype] == 0)
		{
			currhav++;
		}
		else
		{
			tbp[currtype]++;
		}
		tracker[currtype] = true;
		currpick.push_back(nummy.top());
		bytypes[currtype].pop();
		nummy.pop();
	}
	
	if (currhav < k)
	{
		//cout<<"jiuming " <<currhav<<"\n";
		for (int a = 0; a < q; a++)cout << "-1\n";
		return 0;
	}
	//cout << "past second\n";
	
	//cerr << "tracker : " << tracker << " " << currhav << "\n";
	//cerr << "outputting start queue:\n";
	//vector<pii>temp1(currpick.begin(),currpick.end());
	/*for(auto x:temp1)
	{
		cerr<<x.first<<" ";
	}*/
	//cerr << "\ndone\n";
	
	while (tbp[currpick.front().second]>0)
	{
		tbp[currpick.front().second]--;
		currpick.pop_front();
	}
	
	priority_queue<pii,vector<pii>,greater<pii>>queries;
	
	for (int a=0; a < q; a++)
	{
		cin >> t1 >> t2;
		queries.push({t1,a});
	}
	
	vector<int>answers(q);
	while (!queries.empty())
	{
		//cout << "query " << queries.top() << ":\n";
		int currat = queries.top().first;int placeholder = queries.top().second;
		queries.pop();
		//enter till reach currentque
		while ((!nummy.empty())&& nummy.top().first <= currat)
		{
			currpick.push_back(nummy.top());
			int currtype = nummy.top().second;
			bytypes[currtype].pop();
			tbp[currtype]++;
			nummy.pop();
			//cerr<<"pushing in at till u reach me " << currpick.back().first << "\n";
		}
		int currtype = currpick.front().second;
		
		//popping
		while (tbp[currtype] > 0)
		{
			//cerr<<"popping out  " << currpick.front().first << "\n";
			currpick.pop_front();
			tbp[currtype]--;
			currtype = currpick.front().second;
		}
		//while next is more zhide
		while ((!bytypes[currtype].empty()) && (abs(bytypes[currtype].top() - currat) < abs(currpick.front().first - currat)))
		{
			while (nummy.top().second != currtype)
			{
				//cerr<<"pushing in at just getting the better ones" << nummy.top().first << "\n";
				currpick.push_back(nummy.top());
				bytypes[nummy.top().second].pop();
				tbp[nummy.top().second]++;
				nummy.pop();
				currtype = currpick.front().second;
			}
			//cerr<<"pushing in at just getting the better ones" << nummy.top().first << "\n";
			currpick.push_back(nummy.top());
			bytypes[nummy.top().second].pop();
			tbp[nummy.top().second]++;
			nummy.pop();
			currtype = currpick.front().second; 
			while (tbp[currtype] > 0)
			{
				//cerr<<"popping out  " << currpick.front().first << "\n";
				currpick.pop_front();
				tbp[currtype]--;
				currtype = currpick.front().second;
			}  
		}
		currtype = currpick.front().second;
		//popping
		while (tbp[currtype] > 0)
		{
			//cerr<<"popping out  " << currpick.front().first << "\n";
			currpick.front();
			tbp[currtype]--;
			currtype = currpick.front().second;
		}
		answers[placeholder] = (max(abs(currpick.back().first - currat), abs(currpick.front().first-currat)));
	}
	for(int x:answers)cout<<x<<"\n";
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:34:38: warning: unused variable 'currpos' [-Wunused-variable]
   34 |   int currtype = nummy.top().second, currpos = nummy.top().first;
      |                                      ^~~~~~~

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