#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;
typedef pair<pii, int> ppi;
int N, K, Q;
vector<ppp> arr;
vector<ppi> 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];
int iter[MAXN];
vi compress;
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) + 1});
}
void del(int l, int r, int t)
{
// cerr << "del " << l << ' ' << r << " time " << t << endl;
l = (l + r + 1) >> 1;
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);
}
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;
while(iter[w] + 1 < SZ(seg[w]) && seg[w][iter[w] + 1].fi <= x)
{
iter[w]++;
}
if (iter[w] < SZ(seg[w]) && seg[w][iter[w]].fi <= x)
{
res = -x + seg[w][iter[w]].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;
}
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();
iter[i] = 0;
}
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, -2, 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] == -2)
{
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);
}
}
sort(ALL(segments));
FOR(i, 0, SZ(segments))
{
int l = segments[i][2], r = segments[i][3];
inseg(1, 0, SZ(events) + 1, l, r, {segments[i][0], segments[i][1]});
}
//ok cool we have the segments
build(1, 0, SZ(events));
vector<array<int, 3> > queries;
FOR(i, 0, SZ(events))
{
if (events[i][1] == 0)
{
int qid = events[i][2], pos = events[i][3];
queries.PB({pos, i + 1, qid});
}
}
sort(ALL(queries));
for (auto p : queries)
{
ckmax(ans[p[2]], query(1, 0, SZ(events) + 1, p[1], p[0]));
}
}
bool cmp(ppi a, ppi b)
{
return a.fi.se < b.fi.se;
}
int32_t main()
{
if (fopen("file.in", "r"))
{
freopen("file.in", "r", stdin);
freopen("file.out", "w", stdout);
}
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--; arr[i].se.se++;
}
sort(ALL(arr));
FOR(i, 0, Q)
{
cin >> quer[i].fi.fi >> quer[i].fi.se; quer[i].se = i;
compress.PB(quer[i].fi.se);
}
sort(ALL(quer), cmp);
sort(ALL(compress));
compress.erase(unique(ALL(compress)), compress.end());
FOR(i, 0, Q)
{
quer[i].fi.se = LB(ALL(compress), quer[i].fi.se) - compress.begin();
}
FOR(i, 0, N)
{
arr[i].se.fi = LB(ALL(compress), arr[i].se.fi) - compress.begin();
arr[i].se.se = LB(ALL(compress), arr[i].se.se) - compress.begin();
}
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;
}
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';
}
// cerr << "time elapsed = " << clock()/(CLOCKS_PER_SEC / 1000) << " ms " << endl;
return 0;
}
Compilation message
new_home.cpp: In function 'int32_t main()':
new_home.cpp:201: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);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:202:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("file.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
148344 KB |
Output is correct |
| 2 |
Runtime error |
323 ms |
300024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
148344 KB |
Output is correct |
| 2 |
Runtime error |
323 ms |
300024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5130 ms |
428448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
941 ms |
349080 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 |
Correct |
136 ms |
148344 KB |
Output is correct |
| 2 |
Runtime error |
323 ms |
300024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
148344 KB |
Output is correct |
| 2 |
Runtime error |
323 ms |
300024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
