#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long ll;
typedef pair<ll, ll> pll;
#define MAX 301010
#define MAXS 20
#define INF 1000000000
#define MOD (ll)1000000007
#define bb ' '
#define ln '\n'
template <typename T>
class Segment_Tree {
//0-based index Segment Tree
//O(N), O(lgN)
private:
unsigned int N, s;
vector<T> tree;
vector<unsigned int> l, r;
T query(unsigned int low, unsigned int high, unsigned int loc) {
if (low == l[loc] && high == r[loc]) return tree[loc];
if (high <= r[loc * 2]) return query(low, high, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
return query(low, r[loc * 2], loc * 2) + query(l[loc * 2 + 1], high, loc * 2 + 1);
}
void _update(unsigned int loc, T val) {
loc += s;
tree[loc] = val;
loc /= 2;
while (loc) {
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
loc /= 2;
}
}
void init(unsigned int x = 1) {
if (x >= s) {
l[x] = r[x] = x - s;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
tree[x] = tree[x * 2] + tree[x * 2 + 1];
}
public:
Segment_Tree<T>() {
}
Segment_Tree<T>(vector<T>& v) {
N = v.size();
s = 1 << (unsigned int)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
unsigned int i;
for (i = 0; i < N; i++) tree[i + s] = v[i];
init();
}
T query(unsigned int low, unsigned int high) { return query(low, high, 1); }
void update(unsigned int location, T new_value) { _update(location, new_value); }
};
struct dat {
ll x, t, a, b;
dat() {}
dat(ll x, ll t, ll a, ll b) :x(x), t(t), a(a), b(b) {}
bool operator<(dat d) {
if (t != d.t) return t < d.t;
if (x != d.x) return x < d.x;
if (a != d.a) return a < d.a;
return b < d.b;
}
};
struct Query {
ll l, y, num;
Query() {}
Query(ll l, ll y, ll num) :l(l), y(y), num(num) {}
bool operator<(Query q) {
return y < q.y;
}
};
map<ll, vector<dat>> arr;
multiset<ll> st[MAX];
vector<Query> query;
ll ans[MAX];
vector<ll> point, tarr;
vector<pll> larr;
ll chk[MAX];
struct node {
ll x, y;
ll lv, rv;
node() :x(0), y(0), lv(0), rv(-INF) {}
node(ll x, ll y) :x(x), y(y) {
lv = x + y;
rv = y - x;
}
node(ll x, ll y, ll lv, ll rv) :x(x), y(y), lv(lv), rv(rv) {}
node operator+(node x) { return node(0, 0, max(lv, x.lv), max(rv, x.rv)); }
};
bool operator<(pll p1, pll p2) {
if (p1.first == p2.first) return p1.second < p2.second;
return p1.first < p2.first;
}
ll getind(pll x) {
return lower_bound(larr.begin(), larr.end(), x) - larr.begin();
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N, K, Q;
cin >> N >> K >> Q;
ll i;
ll x, t, a, b;
vector<dat> datset;
for (i = 1; i <= N; i++) {
cin >> x >> t >> a >> b;
arr[a].push_back(dat(x, t, a, b));
arr[b + 1].push_back(dat(x, t, a, b));
tarr.push_back(a);
tarr.push_back(b + 1);
}
for (i = 0; i < Q; i++) {
cin >> a >> b;
query.push_back(Query(a, b, i));
}
sort(query.begin(), query.end());
//simulation
for (i = 1; i <= K; i++) st[i].insert(-INF);
for (i = 1; i <= K; i++) st[i].insert(INF);
map<ll, vector<dat>>::iterator it;
for (it = arr.begin(); it != arr.end(); it++) {
t = it->first;
for (auto d : it->second) {
ll pv = *prev(st[d.t].lower_bound(d.x));
ll ne = *st[d.t].upper_bound(d.x);
if (d.a == t) st[d.t].insert(d.x);
else {
larr.emplace_back(pv + ne, d.t);
larr.emplace_back(pv + d.x, d.t);
larr.emplace_back(d.x + ne, d.t);
st[d.t].erase(st[d.t].find(d.x));
}
}
}
Segment_Tree<node> segtree;
vector<node> v(larr.size());
segtree = Segment_Tree<node>(v);
it = arr.begin();
ll cnt = 0;
sort(larr.begin(), larr.end());
larr.erase(unique(larr.begin(), larr.end()), larr.end());
for (i = 0; i < Q; i++) {
Query q = query[i];
while (it != arr.end()) {
ll t = it->first;
if (t > q.y) break;
for (auto d : it->second) {
ll pv = *prev(st[d.t].lower_bound(d.x));
ll ne = *st[d.t].upper_bound(d.x);
if (d.a == t) {
segtree.update(getind({ pv + ne, d.t }), node(pv + ne, 0));
segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, d.x - pv));
segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, ne - d.x));
st[d.t].insert(d.x);
if (!chk[d.t]) cnt++;
chk[d.t]++;
}
else {
st[d.t].erase(st[d.t].find(d.x));
if (chk[d.t] == 1) cnt--;
chk[d.t]--;
if (st[d.t].find(d.x) != st[d.t].end()) continue;
segtree.update(getind({ pv + ne, d.t }), node(pv + ne, ne - pv));
segtree.update(getind({ pv + d.x, d.t }), node(pv + d.x, 0));
segtree.update(getind({ d.x + ne, d.t }), node(d.x + ne, 0));
}
}
it++;
}
if (cnt != K) {
ans[q.num] = -1;
continue;
}
node l = segtree.query(0, getind({ 2 * q.l, 10101010 }) - 1);
node r = segtree.query(getind({ 2 * q.l, -1 }), larr.size() - 1);
ans[q.num] = max(l.lv - 2 * q.l, r.rv + 2 * q.l) / 2;
}
for (i = 0; i < Q; i++) cout << ans[i] << ln;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14396 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14440 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14396 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14440 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2497 ms |
194616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4295 ms |
216904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14396 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14440 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14396 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
14440 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
