#include <algorithm>
#include <iostream>
#include <cassert>
#include <chrono>
#include <vector>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>
#ifdef DEVAL
#define cerr if (false) cerr
#endif
typedef long long llong;
const int MAXN = 300000 + 10;
const int INF = 1e9;
std::mt19937 rngNow(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 rng(69420);
int n, q, k;
struct MergeSortTree
{
struct Treap
{
struct Node
{
Node *left, *right;
int subtreeSize, x, cnt, y;
Node()
{
left = right = nullptr;
}
Node(int _x, int _y)
{
left = right = nullptr;
subtreeSize = cnt = 1;
x = _x; y = _y;
}
};
Node *treap;
void recover(Node *curr)
{
if (curr == nullptr)
{
return;
}
curr->subtreeSize = curr->cnt;
if (curr->left != nullptr)
{
curr->subtreeSize += curr->left->subtreeSize;
}
if (curr->right != nullptr)
{
curr->subtreeSize += curr->right->subtreeSize;
}
}
void split(Node *curr, Node *&left, Node *&right, int k)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (curr->x <= k)
{
left = curr;
split(curr->right, left->right, right, k);
recover(left);
} else
{
right = curr;
split(curr->left, left, right->left, k);
recover(right);
}
}
void merge(Node *&curr, Node *left, Node *right)
{
if (left == nullptr)
{
curr = right;
return;
}
if (right == nullptr)
{
curr = left;
return;
}
if (left->y > right->y)
{
curr = left;
merge(curr->right, left->right, right);
} else
{
curr = right;
merge(curr->left, left, right->left);
}
recover(curr);
}
void insert(int value)
{
Node *l, *ll, *lr, *r;
split(treap, l, r, value);
split(l, ll, lr, value - 1);
if (lr != nullptr)
{
lr->cnt++;
// std::cout << "increment: " << lr->cnt << '\n';
recover(lr);
} else
{
lr = new Node(value, rng());
}
merge(l, ll, lr);
merge(treap, l, r);
}
void erase(int value)
{
Node *l, *ll, *lr, *r;
split(treap, l, r, value);
split(l, ll, lr, value - 1);
assert(lr != nullptr);
if (lr->cnt > 1)
{
lr->cnt--;
// std::cout << "decrement: " << lr->cnt << '\n';
recover(lr);
} else
{
lr = nullptr;
}
merge(l, ll, lr);
merge(treap, l, r);
}
int countLess(int value)
{
int res = 0;
Node *l, *r;
split(treap, l, r, value - 1);
if (l != nullptr) res = l->subtreeSize;
merge(treap, l, r);
return res;
}
};
Treap tree[4*MAXN];
void insert(int l, int r, int node, int queryPos, int queryValue)
{
// std::cout << "insert: " << l << ' ' << r << '\n' << std::flush;
tree[node].insert(queryValue);
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) insert(l, mid, 2*node, queryPos, queryValue);
else insert(mid + 1, r, 2*node + 1, queryPos, queryValue);
}
void erase(int l, int r, int node, int queryPos, int queryValue)
{
// std::cout << "reach: " << l << ' ' << r << '\n' << std::flush;
tree[node].erase(queryValue);
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) erase(l, mid, 2*node, queryPos, queryValue);
else erase(mid + 1, r, 2*node + 1, queryPos, queryValue);
}
int query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node].countLess(queryL);
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
void insert(int pos, int value)
{
insert(1, n, 1, pos, value);
}
void erase(int pos, int value)
{
erase(1, n, 1, pos, value);
}
int query(int l, int r)
{
return query(1, n, 1, l, r);
}
void update(int pos, int oldVal, int newVal)
{
erase(pos, oldVal);
insert(pos, newVal);
}
void build(int a[])
{
for (int i = 1 ; i <= n ; ++i)
{
insert(i, a[i]);
}
}
};
struct Store
{
int pos;
int l, r;
int type;
friend bool operator < (const Store &a, const Store &b)
{
return a.pos < b.pos;
}
};
struct Query
{
int year;
int pos;
int idx;
friend bool operator < (const Query &a, const Query &b)
{
return a.year < b.year;
}
};
struct StoreEvent
{
int year;
int idx;
int t;
friend bool operator < (const StoreEvent &a, const StoreEvent &b)
{
return a.year < b.year;
}
};
int a[MAXN];
int prev[MAXN];
int perm[MAXN];
int output[MAXN];
Store store[MAXN];
Query query[MAXN];
std::set <int> active[MAXN];
std::vector <StoreEvent> storeEvent;
MergeSortTree tree;
int searchLast(int value)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (store[mid].pos <= value) l = mid;
else r = mid;
}
return l;
}
int searchFirst(int value)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (store[mid].pos < value) l = mid;
else r = mid;
}
return r;
}
void solve()
{
std::sort(store + 1, store + 1 + n);
for (int i = 1 ; i <= n ; ++i)
{
storeEvent.push_back({store[i].l, i, 0});
storeEvent.push_back({store[i].r + 1, i, 1});
}
for (int i = 1 ; i <= k ; ++i)
{
active[i].insert(0);
active[i].insert(n + 1);
}
for (int i = 1 ; i <= n ; ++i)
{
prev[i] = INF;
}
int ptr = -1;
tree.build(prev);
std::sort(query + 1, query + 1 + n);
std::sort(storeEvent.begin(), storeEvent.end());
for (int i = 1 ; i <= q ; ++i)
{
while (ptr + 1 < storeEvent.size() && storeEvent[ptr + 1].year <= query[i].year)
{
ptr++;
const auto &[year, idx, t] = storeEvent[ptr];
if (t == 0)
{
auto it = active[store[idx].type].upper_bound(idx);
int next = *it;
if (next <= n) tree.update(next, prev[next], idx);
prev[next] = idx;
it--;
tree.update(idx, prev[idx], *it);
prev[idx] = *it;
active[store[idx].type].insert(idx);
} else
{
auto it = active[store[idx].type].upper_bound(idx);
int next = *it;
if (next <= n) tree.update(next, prev[next], prev[idx]);
prev[next] = prev[idx];
tree.update(idx, prev[idx], INF);
prev[idx] = INF;
active[store[idx].type].erase(active[store[idx].type].find(idx));
}
}
if (tree.query(1, n) < k)
{
output[query[i].idx] = -1;
continue;
}
int l = -1, r = 1e9, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
int ll = searchFirst(query[i].pos - mid);
int rr = searchLast(query[i].pos + mid);
if (ll > rr || tree.query(ll, rr) < k) l = mid;
else r = mid;
}
output[query[i].idx] = r;
}
}
void input()
{
std::cin >> n >> k >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> store[i].pos >> store[i].type >> store[i].l >> store[i].r;
}
for (int i = 1 ; i <= q ; ++i)
{
std::cin >> query[i].pos >> query[i].year;
query[i].idx = i;
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << output[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:337:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<StoreEvent>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
337 | while (ptr + 1 < storeEvent.size() && storeEvent[ptr + 1].year <= query[i].year)
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5030 ms |
358452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
405628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
