#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()
{
//cout<<"hgahwg";
int t1,t2,t3,t4;
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
/*
initial set:
-> at least on eo feach type
int currant -> where youre at now (vector)
bitset of taken; take till typestaken=types; push into vector of vectors
each new one taken:check if currtaken for that one is whats at the bottom
boittom:check bottom for tha tione where ur at now for each ttype
-> replace else no
-> at each stage after all maximums ->take currmxa - currmin
*/
int n,k,q;
cin>>n>>k>>q;
//scout<<"banana";
queue<pii>nottake; //location, type
queue<pii>taken;
vector<vector<int>>bytypes(k+1);
vector<int>currat(k+1,0);
int currnum = 0;
vector<pii>t5;
//cout<<"start\n";
for (int a= 1; a <= n; a++)
{
cin >>t1>>t2>>t3>>t4;
t5.pb({t1,t2});
currnum = currnum | (1<<(t2-1));
}
sort(t5.begin(),t5.end());
for(int a=0;a<n;a++)
{
nottake.push(t5[a]);
bytypes[t5[a].ss].push_back(t5[a].ff);
}
//cout<<"currnum: " << currnum<<"\n";
int constk = k;
int currmin=nottake.front().ff,currmax = INT_MIN;
//cout << "curnrum : " << currnum << "\n";
for (int a=0;a<k;a++)
{
//cout << a << " : " << (currnum & (1<<a) )<< "\n";
if((currnum & (1<<a)) == 0)
{
//cout << "yupe\n";
for(int a = 1; a <=q;a++)
{
cout<<-1 << "\n";
}
return 0;
}
}
//cout<<"yey";
currnum=0; //types taken so far
while(currnum<k)
{
//cout<<"once\n";
t4 = nottake.front().ss;
t3 = nottake.front().ff;
if(currat[t4] == 0)
{
currnum++;
}
currat[t4]++;
taken.push(nottake.front());
nottake.pop();
currmax = taken.back().ff;
//cout << currat[taken.front().ss] - 1 << "\n";
while((!taken.empty()) && (bytypes[taken.front().ss][currat[taken.front().ss] - 1] != taken.front().ff))
{
//cout << "popped it out\n";
taken.pop();
currmin = taken.front().ff;
}
//cout << "reached end\n";
}
//cout << "init " << currmin << " " << currmax << "\n";
vector<int>answers(q+1);
//cout<<"past init\n";
vector<pii>queries;
for(int a=0;a<q;a++)
{
cin>>t1>>t2;
queries.pb({t1,a});
}
sort(queries.begin(),queries.end());
//cout<<"radoifw";
for(int a= 0;a<q;a++)
{
int currque = queries[a].ff;
//cout<<"querying for " << currque<<'\n';
//for including currque
while((!nottake.empty())&&(nottake.front().ff <= currque))
{
taken.push(nottake.front());
nottake.pop();
currmax = taken.back().ff;
currat[taken.back().ss]++;
}
//cout << "ok bruh " << currmin << " " << currmax << "\n";
/*cout<<"after includeing currque:\n";
for(int a=1;a<=k;a++)cout<<currat[a]<<" ";
cout<<'\n';*/
int currtype = taken.front().ss;int currpos=taken.front().ff;
while(bytypes[currtype][currat[currtype] - 1] != currpos)
{
//cout << "once " << bytypes[currtype][currat[currtype] - 1] << " " << currpos << "\n";
taken.pop();
currmin = taken.front().ff;
currpos=taken.front().ff;
currtype = taken.front().ss;
}
/*cout<<"after popping redundant:\n";
for(int a=1;a<=k;a++)cout<<currat[a]<<" ";
cout<<'\n';*/
while((currat[currtype] < bytypes[currtype].size()) && (abs(currque-bytypes[currtype][currat[currtype]]) < abs(currque-bytypes[currtype][currat[currtype]-1])))
{
//cout << "washawasha";
taken.pop();
currmin=taken.front().ff;
taken.push({bytypes[currtype][currat[currtype]],currtype});
currmax = taken.back().ff;
currat[taken.back().ss]++;
}
//cout<<currmin << " " << currmax <<"\n";
answers[queries[a].ss] = max(abs(currmax-currque), abs(currmin-currque));
//vector<int>t6(taken.begin(),taken.end())
}
//cout << "outputting answers:\n";
for (int a = 0; a < q;a++)
{
cout << answers[a] << "\n";
}
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:140:33: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | while((currat[currtype] < bytypes[currtype].size()) && (abs(currque-bytypes[currtype][currat[currtype]]) < abs(currque-bytypes[currtype][currat[currtype]-1])))
new_home.cpp:51:9: warning: unused variable 'constk' [-Wunused-variable]
51 | int constk = k;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
35768 KB |
Output is correct |
| 2 |
Runtime error |
179 ms |
45736 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
30272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
