#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
class Point;
class Query{
public:
int x;
int y;
int ind;
Query() : x(0), y(0) {}
Query(int xx, int yy, int i) : x(xx), y(yy), ind(i) {}
bool operator<(const Query& other) const {
if(y==other.y){
if(x==other.x)return ind<other.ind;
return x<other.x;
}
return y<other.y;
}
bool operator<(const Point& other) const;
};
class Point {
public:
int x;
int t;
int a;
int b;
bool is_erase;
Point() : x(0), t(0), a(0), b(0) {}
Point(int xx, int tt, int aa, int bb, bool er) :
x(xx), t(tt), a(aa), b(bb), is_erase(er) {}
bool operator<(const Point& other) const {
if(other.a==a){
if(other.b==b){
if(other.x==x){
return t<other.t;
}
return x<other.x;
}
return b<other.b;
}
return a<other.a;
}
bool operator<(const Query& other) const {
return a<=other.y;
}
};
bool Query::operator<(const Point& other) const {
return this->y<other.a;
}
class Node {
public:
Query q;
Point p;
bool is_q;
Node(Query qq) : q(qq) {
is_q=true;
}
Node(Point pp) : p(pp) {
is_q=false;
}
bool operator<(const Node& other) const {
if(is_q && other.is_q)return q<other.q;
if(is_q) return q<other.p;
if(other.is_q) return p<other.q;
return p<other.p;
}
};
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
ll n,m,k;
multiset<int>d[N];
vector<Node>s;
int calc_ans(int x){
int ans=0;
for(int i=1;i<=k;i++){
if(d[k].size()==0)return -1;
auto it=d[i].lower_bound(x);
int fd=MOD,sd=MOD;
if(it!=d[i].end()){
fd=*it-x;
}
if(it!=d[i].begin()){
it--;
sd=x-*it;
}
ans=max(ans,min(fd,sd));
}
return ans;
}
int main() {
cin>>n>>k>>m;
for(int i=0;i<n;i++){
int x,t,a,b;
cin>>x>>t>>a>>b;
s.push_back(Node(Point(x,t,a,b,false)));
s.push_back(Node(Point(x,t,b+1,b,true)));
}
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
s.push_back(Node(Query(x,y,i)));
}
sort(s.begin(),s.end());
vector<int>ans(m,-1);
for(int i=0;i<s.size();i++){
if(s[i].is_q){
ans[s[i].q.ind] = calc_ans(s[i].q.x);
}
else{
if(s[i].p.is_erase){
d[s[i].p.t].erase(d[s[i].p.t].find(s[i].p.x));
}
else{
d[s[i].p.t].insert(s[i].p.x);
}
}
}
for(int x:ans)cout<<x<<" ";
cout<<endl;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14376 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14376 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
61300 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5079 ms |
61328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14376 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14376 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
