#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 2100013
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, S;
vector<ppp> arr;
vector<pair<pii, int> > quer;
int ans[MAXN];
multiset<int> pts[MAXN];
vector<array<int, 4> > segments;
vector<array<int, 4> > events;
map<pii, vi> cancer;
vpi seg[MAXN];
void ins(int l, int r, int t)
{
// cerr << "ins " << l << ' ' << r << " time " << t << endl;
l = (l + r + 1) >> 1;
cancer[{l, r}].PB(SZ(segments));
segments.PB({l, r, t, SZ(events)});
}
void del(int l, int r, int t)
{
// cerr << "del " << l << ' ' << r << " time " << t << endl;
l = (l + r + 1) >> 1;
// cerr << "rem " << (cancer[{l, r}]).size() << endl;
segments[cancer[{l, r}].back()][3] = t;
cancer[{l, r}].pop_back();
}
void inseg(int w, int L, int R, int a, int b, pii p)
{
if (a <= L && R <= b)
{
seg[w].PB(p);
return;
}
int mid = (L + R) >> 1;
if (a <= mid) inseg(w << 1, L, mid, a, b, p);
if (mid < b) inseg(w << 1 | 1, mid + 1, R, a, b, p);
return;
}
void build(int w, int L, int R)
{
if (L != R)
{
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
}
sort(ALL(seg[w]));
FOR(i, 1, SZ(seg[w]))
{
ckmax(seg[w][i].se, seg[w][i - 1].se);
}
}
int query(int w, int L, int R, int a, int x)
{
int res = -INF;
int ind = UB(ALL(seg[w]), MP(x, INF)) - seg[w].begin() - 1;
if (ind != -1) res = -x + seg[w][ind].se;
if (L == R) return res;
int mid = (L + R) >> 1;
if (a <= mid) ckmax(res, query(w << 1, L, mid, a, x));
else ckmax(res, query(w << 1 | 1, mid + 1, R, a, x));
return res;
}
bool cmp(pair<pii, int> a, pair<pii, int> b)
{
return a.fi.se < b.fi.se;
}
void solve()
{
//consider distnace functions with negative slope ONLY.
//arr: something of type t and position p in times (t1, t2)
//quer: query of position p at time t, qid i
FOR(i, 0, (1 << (33 - __builtin_clz(SZ(events)))))
{
seg[i].clear();
}
events.clear();
cancer.clear();
segments.clear();
FOR(i, 0, K) pts[i].clear();
FOR(i, 0, SZ(arr))
{
int t1 = arr[i].se.fi, t2 = arr[i].se.se, ty = arr[i].fi.fi, x = arr[i].fi.se;
events.PB({t1, -1, ty, x});
events.PB({t2, 1, ty, x});
}
// FOR(i, 0, SZ(quer))
// {
// int t = quer[i].fi.se, x = quer[i].fi.fi, qid = quer[i].se;
// events.PB({t, 0, qid, x});
// }
sort(ALL(events));
FOR(i, 0, K)
{
pts[i].insert(2 * LIM);
pts[i].insert(-2 * LIM);
ins(-2 * LIM, 2 * LIM, 0);
}
FOR(i, 0, SZ(events))
{
int typ = events[i][2], pos = events[i][3];
if (events[i][1] == -1)
{
auto it = pts[typ].UB(pos);
int rt = *it, lt = *prev(it);
pts[typ].insert(pos);
//then between lt and rt you generate some new segments!
//at time i you have to erase a segment! and then insert two new segments!
//WARNING: IF NOT DISTINCT, PLEASE CHECK THIS PLACE
ins(lt, pos, i + 1);
ins(pos, rt, i + 1);
del(lt, rt, i + 1);
}
if (events[i][1] == 1)
{
pts[typ].erase(pts[typ].find(pos));
auto it = pts[typ].UB(pos);
int rt = *it, lt = *prev(it);
del(lt, pos, i + 1);
del(pos, rt, i + 1);
ins(lt, rt, i + 1);
}
}
FOR(i, 0, SZ(segments))
{
int l = segments[i][2], r = segments[i][3];
inseg(1, 0, SZ(events), l, r, {segments[i][0], segments[i][1]});
}
//ok cool we have the segments
build(1, 0, SZ(events));
// FOR(i, 0, SZ(quer))
// {
// int t = quer[i].fi.se, x = quer[i].fi.fi, qid = quer[i].se;
// events.PB({t, 0, qid, x});
// }
// FOR(i, 0, Q)
// {
// cerr << quer[i].fi.se << ' ';
// }
// cerr << endl;
int iter = 0;
FOR(i, 0, SZ(events))
{
if (events[i][1] == 1)
{
while(iter < Q && quer[iter].fi.se <= events[i][0])
{
int x = quer[iter].fi.fi, qid = quer[iter].se;
ckmax(ans[qid], query(1, 0, SZ(events), i, x));
iter++;
}
}
// if (events[i][1] == 0)
// {
// int qid = events[i][2], pos = events[i][3];
// ckmax(ans[qid], query(1, 0, SZ(events), i + 1, pos));
// // cerr << "ans " << qid << ' ' << ans[qid] << endl;
// }
}
while(iter < Q)
{
int x = quer[iter].fi.fi, qid = quer[iter].se;
ckmax(ans[qid], query(1, 0, SZ(events), SZ(events), x));
iter++;
}
}
int32_t main()
{
if (fopen("file.in", "r"))
{
freopen("file.in", "r", stdin);
}
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K >> Q;
arr.resize(N); quer.resize(Q);
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.fi >> quer[i].fi.se; quer[i].se = i;
}
sort(ALL(quer), cmp);
solve();
FOR(i, 0, N)
{
arr[i].fi.se = 100000001 - arr[i].fi.se;
}
FOR(i, 0, Q)
{
quer[i].fi.fi = 100000001 - quer[i].fi.fi;
}
// reverse(ALL(quer));
solve();
//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;
}
// cerr << "ans " << ans[i] << endl;
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
new_home.cpp: In function 'int32_t main()':
new_home.cpp:213:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("file.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
148472 KB |
Output is correct |
| 2 |
Correct |
151 ms |
148408 KB |
Output is correct |
| 3 |
Correct |
140 ms |
148340 KB |
Output is correct |
| 4 |
Incorrect |
158 ms |
148344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
148472 KB |
Output is correct |
| 2 |
Correct |
151 ms |
148408 KB |
Output is correct |
| 3 |
Correct |
140 ms |
148340 KB |
Output is correct |
| 4 |
Incorrect |
158 ms |
148344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5103 ms |
386740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5129 ms |
413956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
148472 KB |
Output is correct |
| 2 |
Correct |
151 ms |
148408 KB |
Output is correct |
| 3 |
Correct |
140 ms |
148340 KB |
Output is correct |
| 4 |
Incorrect |
158 ms |
148344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
148472 KB |
Output is correct |
| 2 |
Correct |
151 ms |
148408 KB |
Output is correct |
| 3 |
Correct |
140 ms |
148340 KB |
Output is correct |
| 4 |
Incorrect |
158 ms |
148344 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
