Submission #977199

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
977199	2024-05-07T13:43:20 Z	vjudge1	New Home (APIO18_new_home)	C++17	10 / 100	302 ms	58928 KB

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

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

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	295 ms	45208 KB	Output is correct
2	Correct	265 ms	35608 KB	Output is correct
3	Correct	292 ms	58000 KB	Output is correct
4	Correct	290 ms	46416 KB	Output is correct
5	Correct	281 ms	36852 KB	Output is correct
6	Correct	302 ms	36880 KB	Output is correct
7	Correct	280 ms	58928 KB	Output is correct
8	Correct	263 ms	44840 KB	Output is correct
9	Correct	255 ms	41752 KB	Output is correct
10	Correct	277 ms	36128 KB	Output is correct
11	Correct	232 ms	36428 KB	Output is correct
12	Correct	233 ms	36304 KB	Output is correct