#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define LIM 100000007
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 600013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;
int N, K, Q, P;
vector<ppp> arr;
pii quer[MAXN];
int ans[MAXN];
vi compress, pos;
vpi func;
int mx, iter, freq;
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K >> Q;
arr.resize(N);
FOR(i, 0, N)
{
cin >> arr[i].fi.se >> arr[i].fi.fi >> arr[i].se.fi >> arr[i].se.se;
arr[i].fi.fi--;
}
FOR(i, 0, Q)
{
cin >> quer[i].fi >> quer[i].se; //location, time
compress.PB(quer[i].se);
}
compress.PB(0); compress.PB(LIM);
sort(ALL(compress));
compress.erase(unique(ALL(compress)), compress.end());
FOR(i, 0, N)
{
arr[i].se.fi = LB(ALL(compress), arr[i].se.fi) - compress.begin();
arr[i].se.se = UB(ALL(compress), arr[i].se.se) - compress.begin() - 1;
}
FOR(i, 0, Q)
{
quer[i].se = LB(ALL(compress), quer[i].se) - compress.begin();
}
//type, location, times (whaever)
//ok this is type what:
sort(ALL(arr));
freq = 0;
FOR(i, 0, N)
{
//consider the distance functions formed! query max!
//so for each of the things you should have shit of the form: a distance function that starts at time t that has x-intercept t1
pos.PB(arr[i].fi.se);
if (i == N - 1 || arr[i].fi.fi != arr[i + 1].fi.fi)
{
//build the shit! how about let's try the negatives first
func.PB({0, pos[0]});
// cerr << 0 << ' ' << pos[0] << endl;
FOR(j, 1, SZ(pos))
{
func.PB({(pos[j - 1] + pos[j] + 1) >> 1, pos[j]});
}
pos.clear();
freq++;
}
}
if (freq != K)
{
func.PB({0, INF});
}
sort(ALL(func));
mx = -INF; iter = 0;
FOR(i, 0, SZ(func))
{
while(iter < Q && quer[iter].fi < func[i].fi)
{
ckmax(ans[iter], -quer[iter].fi + mx);
iter++;
}
ckmax(mx, func[i].se);
// cerr << "at location " << func[i].fi << " -x + " << func[i].se << endl;
}
while(iter < Q)
{
ckmax(ans[iter], -quer[iter].fi + mx);
iter++;
}
// freq = 0; func.clear();
// FOR(i, 0, N)
// {
// pos.PB(arr[i].fi.se);
// if (i == N - 1 || arr[i].fi.fi != arr[i + 1].fi.fi)
// {
// //build the shit! how about let's try the negatives first
// func.PB({LIM, -pos.back()});
// FORD(j, SZ(func) - 1, 0)
// {
// func.PB({(pos[j] + pos[j + 1]) >> 1, -pos[j]});
// }
// pos.clear();
// freq++;
// }
// }
// if (freq != K)
// {
// func.PB({LIM, INF});
// }
// sort(ALL(func));
// mx = -INF; iter = Q - 1;
// FORD(i, SZ(func), 0)
// {
// while(iter >= 0 && quer[iter].fi > func[i].fi)
// {
// ckmax(ans[iter], quer[iter].fi + mx);
// iter--;
// }
// ckmax(mx, func[i].se);
// // cerr << "at location " << func[i].fi << " x + " << func[i].se << endl;
// }
// while(iter >= 0)
// {
// ckmax(ans[iter], quer[iter].fi + mx);
// iter--;
// }
//events: OPEN/CLOSE a store at time t, position p, type x, ASK at time t, position p
FOR(i, 0, Q)
{
if (ans[i] >= LIM)
{
cout << "-1\n";
continue;
}
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
431 ms |
15096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
15072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
