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 lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int K = 405;
int n, k, q;
vector<array<int, 4> > ev;
vector<array<int, 3> > qu;
vector<multiset<int> > st(K);
void solve() {
cin >> n >> k >> q;
REP(i, n) {
int x, t, a, b;
cin >> x >> t >> a >> b;
ev.pb({a, x, t, 1});
ev.pb({b + 1, x, t, 0});
}
qu.resize(q);
REP(i, q) {
cin >> qu[i][1] >> qu[i][0];
qu[i][2] = i;
}
sort(all(qu));
sort(all(ev));
int ind = 0;
vector<int> res(q, 0);
for(auto c : qu) {
while(ind < ev.size() && ev[ind][0] <= c[0]) {
if(ev[ind][3]) {
st[ev[ind][2]].insert(ev[ind][1]);
}
else {
st[ev[ind][2]].erase(st[ev[ind][2]].lower_bound(ev[ind][1]));
}
ind++;
}
int mx = 0;
for(int i = 1; i <= k; i++) {
if(st[i].empty()) {
mx = -1;
break;
}
auto itr = st[i].lower_bound(c[1]);
int mn = INF;
if(itr != st[i].end()) mn = min(mn, (*itr) - c[1]);
if(itr != st[i].begin()) {
itr--;
mn = min(mn, c[1] - (*itr));
}
mx = max(mx, mn);
}
res[c[2]] = mx;
}
REP(i, q) {
cout << res[i] << "\n";
}
}
signed main() {
fastio();
solve();
}
Compilation message (stderr)
new_home.cpp: In function 'void solve()':
new_home.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | while(ind < ev.size() && ev[ind][0] <= c[0]) {
| ~~~~^~~~~~~~~~~
# | 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... |