#include <bits/stdc++.h>
using namespace std;
const int N = 300005, M = 60004;
int n, q, k;
int ans[N];
struct ban0
{
int x;
int u;
int t;
int i;
ban0(){}
ban0(int x, int u, int t, int i)
{
this->x = x;
this->u = u;
this->t = t;
this->i = i;
}
};
bool operator<(const ban0& a, const ban0& b)
{
if (a.u < b.u)
return true;
if (a.u > b.u)
return false;
if (a.t == 0)
return false;
if (b.t == 0)
return true;
return false;
}
bool so(const ban0& a, const ban0& b)
{
if (a.u > b.u)
return true;
if (a.u < b.u)
return false;
if (a.t == 0)
return true;
if (b.t == 0)
return false;
return false;
}
void solv0()
{
vector<ban0> v;
for (int i = 1; i <= n; ++i)
{
int x, t, l, r;
cin >> x >> t >> l >> r;
v.push_back(ban0(x, l, t, i));
v.push_back(ban0(x, r + 1, -t, i));
}
for (int i = 1; i <= q; ++i)
{
int x, u;
cin >> x >> u;
v.push_back(ban0(x, u, 0, i));
}
sort(v.begin(), v.end());
multiset<int> s[M];
for (int ii = 0; ii < v.size(); ++ii)
{
int x = v[ii].x;
int t = v[ii].t;
if (t > 0)
{
s[t].insert(x);
}
else if (t < 0)
{
s[-t].erase(s[-t].find(x));
}
else
{
bool z = false;
int maxu = 0;
for (int i = 1; i <= k; ++i)
{
if (s[i].empty())
{
z = true;
break;
}
multiset<int>::iterator it = s[i].lower_bound(x);
int minu = 1000000000;
if (it != s[i].end())
minu = abs(*it - x);
--it;
if (it != s[i].end())
minu = min(minu, abs(*it - x));
maxu = max(maxu, minu);
}
if (z)
ans[v[ii].i] = -1;
else
ans[v[ii].i] = maxu;
}
}
for (int i = 1; i <= q; ++i)
cout << ans[i] << endl;
}
void solv01()
{
bool c[N] = {};
vector<ban0> v;
for (int i = 1; i <= n; ++i)
{
int x, t, l, r;
cin >> x >> t >> l >> r;
v.push_back(ban0(x, 0, t, k));
c[t] = true;
}
for (int i = 1; i <= q; ++i)
{
int x, u;
cin >> x >> u;
v.push_back(ban0(x, 0, 0, i));
}
for (int i = 1; i <= k; ++i)
{
if (!c[i])
{
for (int i = 1; i <= q; ++i)
cout << -1 << endl;
return;
}
}
int g[N] = {};
multiset<int> s;
sort(v.begin(), v.end());
for (int ii = 0; ii < v.size(); ++ii)
{
int x = v[ii].x;
int t = v[ii].t;
if (t)
{
if (!g[t])
s.erase(g[t]);
s.insert(x);
g[t] = x;
}
else
{
if (!s.empty())
ans[v[ii].i] = abs(*s.begin() - x);
}
}
memset(g, 0, sizeof g);
s.clear();
sort(v.begin(), v.end(), so);
for (int ii = 0; ii < v.size(); ++ii)
{
int x = v[ii].x;
int t = v[ii].t;
if (t)
{
if (!g[t])
s.erase(g[t]);
s.insert(x);
g[t] = x;
}
else
{
if (!s.empty())
ans[v[ii].i] = max(ans[v[ii].i], abs(*s.begin() - x));
}
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << endl;
}
int main()
{
//freopen("input.txt", "r", stdin);
cin >> n >> k >> q;
//if (n <= 60000 && k <= 400)
// solv0();
//else
solv01();
return 0;
}
Compilation message
new_home.cpp: In function 'void solv0()':
new_home.cpp:67:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii = 0; ii < v.size(); ++ii)
~~~^~~~~~~~~~
new_home.cpp: In function 'void solv01()':
new_home.cpp:141:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii = 0; ii < v.size(); ++ii)
~~~^~~~~~~~~~
new_home.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii = 0; ii < v.size(); ++ii)
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
3584 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 |
7 ms |
3584 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 |
1061 ms |
52876 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 |
999 ms |
52788 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 |
7 ms |
3584 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 |
7 ms |
3584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
