/*
We will use sweep line to solve the problem. We split the stores into 2 queries:
1) Add store i at time a[i]
2) Remove store i at time b[i] + 1
We will also have queries in the sweep line. Everything will be sorted by time in increasing order.
Now to handle queries we will maintain K sets - the available positions of j-type stores. Then if A and B are two consecutive stores, the closest elements to all positions in [A; B] are A or B.
Then let's have a two segment trees wtih sets - one for closest elements to the left and one for closest elements to the right. Now addition of store with type X will be done like that:
1) Let A <= X <= B and A and B are the closest stores of the same type. Then we will remove -A from the first segment tree and B from the second tree from the interval [A; B].
2) We add -A to [A; X] in the first tree.
3) We add X to [A; X] in the second tree.
4) We add -X to [X; B] in the first tree.
5) We add B to [X; B] in the second tree.
Now query is simply getting maximum and minimum on the path from root to the corresponding leaf.
The complexity will be O(N * log N * log N).
As sets are slow, we will compress the input in each segment tree node beforehand and then use priority queue instead of sets.
*/
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int inf = (int)1e9 + 42;
int n, k, q;
struct event
{
int type;
int T, x, tp, idx;
event() { type = tp = T = x = 0; idx = -1; }
event(int t, int Tm, int X, int i, int pp = -1)
{
type = t;
T = Tm;
x = X;
idx = i;
tp = pp;
}
};
bool cmp(event a, event b)
{
if(a.T != b.T) return a.T < b.T;
return a.type < b.type;
}
vector<event> Ev;
int answer[MAXN];
vector<int> Xcord;
int get(int x) { return L_B(ALL(Xcord), x) - Xcord.begin(); }
void read()
{
cin >> n >> k >> q;
for(int i = 0; i < n; i++)
{
int x, t, a, b;
cin >> x >> t >> a >> b;
Ev.push_back(event(0, a, x, i, t));
Ev.push_back(event(1, b + 1, x, i, t));
Xcord.push_back(x);
}
for(int i = 0; i < q; i++)
{
int x, t;
cin >> x >> t;
Ev.push_back(event(2, t, x, i));
Xcord.push_back(x);
}
}
set<pair<int, int> > ST[MAXN];
void add_mids(int l, int r)
{
int mid = (l + r) / 2;
Xcord.push_back(mid);
Xcord.push_back(mid + 1);
}
void prep_compr_add(int y, int x, int i)
{
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
ST[y].insert({x, i});
add_mids(bef->first, x);
add_mids(x, aft->first);
}
void prep_compr_rem(int y, int x, int i)
{
ST[y].erase({x, i});
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
add_mids(bef->first, aft->first);
}
struct segment_tree
{
vector<int> li[4 * MAXN];
priority_queue<pair<int, int> > q[4 * MAXN];
vector<int> cnt[4 * MAXN];
void init(int l, int r, int idx)
{
sort(ALL(li[idx]));
li[idx].erase(unique(ALL(li[idx])), li[idx].end());
cnt[idx].assign(SZ(li[idx]), 0);
if(l == r) return;
int mid = (l + r) >> 1;
init(l, mid, 2 * idx + 1);
init(mid + 1, r, 2 * idx + 2);
}
void fix(int idx)
{
while(!q[idx].empty() && cnt[idx][q[idx].top().second] >= 1)
{
cnt[idx][q[idx].top().second]--;
q[idx].pop();
}
}
void add_to_prep(int ql, int qr, int v, int l, int r, int idx)
{
if(ql > r || qr < l)
return;
if(ql <= l && r <= qr)
{
li[idx].push_back(v);
return;
}
int mid = (l + r) >> 1;
add_to_prep(ql, qr, v, l, mid, 2 * idx + 1);
add_to_prep(ql, qr, v, mid + 1, r, 2 * idx + 2);
}
void add(int ql, int qr, int v, int l, int r, int idx)
{
if(ql > r || qr < l)
return;
if(ql <= l && r <= qr)
{
int o = L_B(ALL(li[idx]), v) - li[idx].begin();
q[idx].push({v, o});
fix(idx);
return;
}
int mid = (l + r) >> 1;
add(ql, qr, v, l, mid, 2 * idx + 1);
add(ql, qr, v, mid + 1, r, 2 * idx + 2);
}
void rem(int ql, int qr, int v, int l, int r, int idx)
{
if(ql > r || qr < l)
return;
if(ql <= l && r <= qr)
{
int o = L_B(ALL(li[idx]), v) - li[idx].begin();
cnt[idx][o]++;
fix(idx);
return;
}
int mid = (l + r) >> 1;
rem(ql, qr, v, l, mid, 2 * idx + 1);
rem(ql, qr, v, mid + 1, r, 2 * idx + 2);
}
int query(int x, int l, int r, int idx)
{
if(l == r)
{
fix(idx);
return !q[idx].empty() ? q[idx].top().first : 0;
}
int mid = (l + r) >> 1;
int val = !q[idx].empty() ? q[idx].top().first : 0;
if(x <= mid)
chkmax(val, query(x, l, mid, 2 * idx + 1));
else
chkmax(val, query(x, mid + 1, r, 2 * idx + 2));
return val;
}
} L, R;
void prep_add_interval(int l, int r)
{
int mid = (l + r) / 2;
if(l <= mid) L.add_to_prep(get(l), get(mid), -l, 0, SZ(Xcord), 0);
if(mid <= r) R.add_to_prep(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}
void prep_add(int y, int x, int i)
{
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
ST[y].insert({x, i});
prep_add_interval(bef->first, x);
prep_add_interval(x, aft->first);
}
void prep_rem(int y, int x, int i)
{
ST[y].erase({x, i});
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
prep_add_interval(bef->first, aft->first);
}
void add_interval(int l, int r)
{
int mid = (l + r) / 2;
if(l <= mid) L.add(get(l), get(mid), -l, 0, SZ(Xcord), 0);
if(mid <= r) R.add(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}
void rem_interval(int l, int r)
{
int mid = (l + r) / 2;
if(l <= mid) L.rem(get(l), get(mid), -l, 0, SZ(Xcord), 0);
if(mid <= r) R.rem(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}
int query(int x) { return max(x + L.query(get(x), 0, SZ(Xcord), 0), R.query(get(x), 0, SZ(Xcord), 0) - x); }
void add(int y, int x, int i)
{
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
ST[y].insert({x, i});
rem_interval(bef->first, aft->first);
add_interval(bef->first, x);
add_interval(x, aft->first);
}
void rem(int y, int x, int i)
{
ST[y].erase({x, i});
auto aft = ST[y].L_B({x, i});
auto bef = prev(aft);
rem_interval(bef->first, x);
rem_interval(x, aft->first);
add_interval(bef->first, aft->first);
}
void solve()
{
Xcord.push_back(inf);
Xcord.push_back(-inf);
Xcord.push_back(0);
Xcord.push_back(1);
for(int i = 1; i <= k; i++)
ST[i].insert({-inf, -1}), ST[i].insert({inf, -1});
sort(ALL(Ev), cmp);
for(auto it: Ev)
if(it.type == 0)
prep_compr_add(it.tp, it.x, it.idx);
else if(it.type == 1)
prep_compr_rem(it.tp, it.x, it.idx);
sort(ALL(Xcord));
Xcord.erase(unique(ALL(Xcord)), Xcord.end());
for(auto it: Ev)
if(it.type == 0)
prep_add(it.tp, it.x, it.idx);
else if(it.type == 1)
prep_rem(it.tp, it.x, it.idx);
prep_add_interval(-inf, inf);
L.init(0, SZ(Xcord), 0);
R.init(0, SZ(Xcord), 0);
for(auto it: Ev)
if(it.type == 0)
add(it.tp, it.x, it.idx);
else if(it.type == 1)
rem(it.tp, it.x, it.idx);
else
answer[it.idx] = query(it.x);
for(int i = 0; i < q; i++)
if(answer[i] < (int)2e8) cout << answer[i] << endl;
else cout << -1 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
706396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
706396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5146 ms |
908308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5129 ms |
908308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
706396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
671 ms |
706396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
