#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()
{
int t1,t2,t3,t4;
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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);
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, tracker = 0;
while ((!nummy.empty()) && currhav < k)
{
int currtype = nummy.top().second, currpos = nummy.top().first;
if (((1 << currtype) & (tracker)) == 0)
{
currhav++;
}
else
{
tbp[currtype]++;
}
tracker |= (1<<currtype);
currpick.push_back(nummy.top());
bytypes[currtype].pop();
nummy.pop();
}
if (currhav < k)
{
for (int a = 0; a < q; a++)cout << "-1\n";
}
//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<int,vector<int>,greater<int>>queries;
for (int a=0; a < q; a++)
{
cin >> t1 >> t2;
queries.push(t1);
}
while (!queries.empty())
{
//cout << "query " << queries.top() << ":\n";
int currat = queries.top();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;
}
cout << max(abs(currpick.back().first - currat), abs(currpick.front().first-currat)) << "\n";;
}
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:33:38: warning: unused variable 'currpos' [-Wunused-variable]
33 | int currtype = nummy.top().second, currpos = nummy.top().first;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
959 ms |
48584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
907 ms |
42800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
