#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
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;
}
struct custom_hash
{
template<class T>
unsigned long long operator()(T v) const
{
unsigned long long x = v;
x = (x ^ (x >> 27));
return x;
}
};
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;
#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 300013
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, S;
ppp arr[MAXN];
ppi quer[MAXN];
int ans[MAXN];
multiset<int> pts[MAXN];
vector<array<int, 4> > segments;
vector<array<int, 4> > events;
hash_table<ll, vi> cancer;
vpi seg[MAXN << 2];
int iter[MAXN << 2];
vi compress;
void ins(int l, int r, int t)
{
l = (l + r + 1) >> 1;
cancer[1ll * INF * l + r].PB(SZ(segments));
segments.PB({l, r, t, Q + 2});
}
void del(int l, int r, int t)
{
l = (l + r + 1) >> 1;
auto it = cancer.find(1ll * INF * l + r);
segments[it -> se.back()][3] = t;
it -> se.pop_back();
}
void inseg(int w, int L, int R, int a, int b, pii p)
{
if (a <= L && R <= b)
{
if (seg[w].empty() || p.se > seg[w].back().se) 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;
}
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()
{
FOR(i, 0, (1 << (33 - __builtin_clz(Q + 2))) + 1)
{
seg[i].clear();
iter[i] = 0;
}
events.clear();
cancer.clear();
segments.clear();
FOR(i, 0, K) pts[i].clear();
FOR(i, 0, N)
{
int t1 = arr[i].se.fi, t2 = arr[i].se.se, ty = arr[i].fi.fi, x = arr[i].fi.se;
if (t1 == t2) continue;
events.PB({t1, -1, ty, x});
events.PB({t2, -2, ty, 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 t = events[i][0], 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);
ins(lt, pos, t + 1);
ins(pos, rt, t + 1);
del(lt, rt, t);
}
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, t);
del(pos, rt, t);
ins(lt, rt, t + 1);
}
}
sort(ALL(segments));
FOR(i, 0, SZ(segments))
{
int l = segments[i][2], r = segments[i][3];
if (l > r) continue;
inseg(1, 0, Q + 2, l, r, {segments[i][0], segments[i][1]});
}
FOR(i, 0, Q)
{
ckmax(ans[quer[i].se], query(1, 0, Q + 2, quer[i].fi.se + 1, quer[i].fi.fi));
}
}
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;
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++;
}
FOR(i, 0, Q)
{
cin >> quer[i].fi.fi >> quer[i].fi.se; quer[i].se = i;
compress.PB(quer[i].fi.se);
}
compress.PB(INF);
compress.PB(0);
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();
}
sort(arr, arr + N);
sort(quer, quer + Q);
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(quer, quer + Q);
solve();
FOR(i, 0, Q)
{
if (ans[i] >= LIM)
{
cout << "-1\n";
continue;
}
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:180: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:181: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 |
Incorrect |
40 ms |
42616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
42616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3492 ms |
285168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5118 ms |
281780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
42616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
42616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
