This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
#define int long long
using namespace std;
struct st{
int x;
int t;
int a;
int b;
st(int q,int w,int e,int r){
x = q;
t = w;
a = e;
b = r;
}
};
struct st2{
int l;
int y;
int id;
st2(int a,int b,int c){
l = a;
y = b;
id = c;
}
};
struct st3{
int ans;
int id;
bool operator<(st3 b)const{
return id < b.id;
}
st3(int a,int b){
ans = a;
id = b;
}
};
const int maxn = 3e6;
unordered_map<int,int> unirl,irl;
vector<st2> query[maxn];
vector<st> del[maxn],add[maxn];
int cnt[maxn];
int n,q,k;
vector<st3> res;
void solve(){
multiset<int> now;
int all = 0;
for(int i(0); i < maxn;i++){
while(add[i].size()){
if(cnt[add[i].back().t] == 0){
all++;
}
cnt[add[i].back().t]++;
now.insert(add[i].back().x);
add[i].pop_back();
}
while(del[i].size()){
if(cnt[del[i].back().t] == 1){
all--;
}
cnt[del[i].back().t]--;
now.erase(now.find(del[i].back().x));
del[i].pop_back();
}
for(int j(0); j < query[i].size();j++){
if(all!=k || !now.size()){
res.push_back(st3(-1,query[i][j].id));
continue;
}
//cout << irl[i] << ' ' << all << ' ' << now.size() << endl;
int l,r;
l = *now.begin();
r = *(--now.end());
int x = query[i][j].l;
//cout << "w " << x << endl;
res.push_back(st3(max(abs(l-x),abs(r-x)),query[i][j].id));
}
}
}
main()
{
ios_base::sync_with_stdio(0);
cin >> n >> k >> q;
set<int> s;
vector<st> v;
for(int i(0); i < n;i++){
int x,t,a,b; cin >> x >> t >> a >> b;
s.insert(a);
s.insert(b);
v.push_back(st(x,t,a,b));
}
vector<st2> qwe;
for(int i(0); i < q;i++){
int l,y; cin >> l >> y;
s.insert(y);
qwe.push_back(st2(l,y,i));
}
int pnt = 0;
for(auto& a:s){
unirl[a] = pnt;
irl[pnt] = a;
pnt++;
}
for(int i(0); i < v.size();i++){
del[unirl[v[i].b]+1].push_back(v[i]);
add[unirl[v[i].a]].push_back(v[i]);
}
for(int i(0); i < qwe.size();i++){
query[unirl[qwe[i].y]].push_back(qwe[i]);
}
solve();
sort(res.begin(),res.end());
for(int i(0); i < res.size();i++){
cout << res[i].ans << '\n';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message (stderr)
new_home.cpp: In function 'void solve()':
new_home.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j(0); j < query[i].size();j++){
~~^~~~~~~~~~~~~~~~~
new_home.cpp: At global scope:
new_home.cpp:90:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
new_home.cpp: In function 'int main()':
new_home.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < v.size();i++){
~~^~~~~~~~~~
new_home.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < qwe.size();i++){
~~^~~~~~~~~~~~
new_home.cpp:123:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < res.size();i++){
~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |