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, 2> > qu;
vector<multiset<int> > st(K);
vector<vector<int> > ev(N);
vector<array<int, 3> > eve; // occ, x, 0 or 1
vector<int> pt(N, 0);
void solve() {
cin >> n >> k >> q;
REP(i, n) {
int x, t, a, b;
cin >> x >> t >> a >> b;
ev[t].pb(x);
}
qu.resize(q);
REP(i, q) {
cin >> qu[i][0];
qu[i][1] = i;
}
sort(all(qu));
bool emp = 0;
for(int i = 1; i <= k; i++) {
sort(all(ev[i]));
if(ev[i].empty()) {
emp = 1;
break;
}
int tm = 1;
for(int j = 0; j < ev[i].size(); j++) {
eve.pb({tm, ev[i][j], 1});
if(j == ev[i].size() - 1) continue;
eve.pb({ev[i][j + 1] + ev[i][j] / 2, ev[i][j], 0});
}
}
if(emp) {
REP(i, q) cout << "-1\n";
return;
}
sort(all(eve));
multiset<int> st;
int ind = 0;
vector<int> res(q, 0);
for(auto c : qu) {
while(ind < eve.size() && eve[ind][0] <= c[0]) {
if(eve[ind][2]) {
st.insert(eve[ind][1]);
}
else {
st.erase(st.lower_bound(eve[ind][1]));
}
}
int mx = 0;
mx = max(mx, abs(c[0] - (*st.begin())));
mx = max(mx, abs((*prev(st.end())) - c[0]));
res[c[1]] = 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:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int j = 0; j < ev[i].size(); j++) {
| ~~^~~~~~~~~~~~~~
new_home.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if(j == ev[i].size() - 1) continue;
| ~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | while(ind < eve.size() && eve[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... |