#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <bitset>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;
const ll MOD = 1000000007, N =300010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -7230040172838, MAX = 7230040172838;
const int S = 60;
ll mn(ll a, ll b) {
if (a == -1)return b;
if (b == -1)return a;
return min(a, b);
}
static ll gcd(ll v1, ll v2) {
if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}
ll pw(ll v1, ll v2) {
ll v3 = 1;
while (v2 > 0) {
if (v2 % 2)v3 = (v3*v1) % MOD;
v1 = (v1*v1) % MOD;
v2 /= 2;
}
return v3;
}
int n, Q, as[N], k, id[N];
pos ql[N];
vector<int> ls[N];
priority_queue<pos> q,q2;
multiset<int> mnl, mxl;
int main() {
cin >> n >> k >> Q;
for (int i = 1; i <= n; i++) {
int v1, v2, v3, v4;
cin >> v1 >> v2 >> v3 >> v4;
ls[v1].pb(v2);
}
for (int i = 1; i <= k; i++) {
sort(ls[i].begin(), ls[i].end());
if (ls[i].empty()) {
for (int i = 0; i < Q; i++)cout << -1 << endl;
return 0;
}
q.push(mk(-ls[i][0], i));
mxl.insert(-ls[i][0]);
}
for (int i = 0; i < Q; i++) {
ll v1, v2; cin >> v1 >> v2;
ql[i] = mk(v2, i);
}
sort(ql, ql + Q);
for (int qi = 0; qi < Q; qi++) {
while (!q2.empty() && -q2.top().first <= ql[qi].first) {
ll ci = -q2.top().first; q2.pop();
if (id[ci] != 0) { mnl.erase(mnl.find(ls[ci][id[ci] - 1])); }
mxl.insert(-ls[ci][id[ci]]);
}
while (!q.empty() && -q.top().first <= ql[qi].first) {
ll lv = -q.top().first, ci = q.top().second;
q.pop();
id[ci]++;
if(id[ci]<ls[ci].size())
q.push(mk(-ls[ci][id[ci]], ci));
mxl.erase(mxl.find(-lv));
mnl.insert(lv);
ll nv;
if (id[ci] < ls[ci].size())nv = (ls[ci][id[ci]] + lv) / 2;
else nv = MAX;
q2.push(mk(-nv, ci));
}
while (!q2.empty() && -q2.top().first <= ql[qi].first) {
int ci = -q2.top().first; q2.pop();
if (id[ci] != 0) { mnl.erase(mnl.find(ls[ci][id[ci] - 1])); }
mxl.insert(-ls[ci][id[ci]]);
}
ll v1 = abs(*mxl.begin()), v2 = abs(*mnl.begin()),v3=ql[qi].first;
as[ql[qi].second] = max(abs(v1 - v3), abs(v2 - v3));
}
for (int i = 0; i < Q; i++)cout << as[i] << endl;
return 0;
}
Compilation message
new_home.cpp: In function 'll gcd(ll, ll)':
new_home.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
^~
new_home.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
^~
new_home.cpp: In function 'int main()':
new_home.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(id[ci]<ls[ci].size())
~~~~~~^~~~~~~~~~~~~~
new_home.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (id[ci] < ls[ci].size())nv = (ls[ci][id[ci]] + lv) / 2;
~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
14592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
14584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
