#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <tuple>
using namespace std;
#pragma warning (disable: 4996)
class SegmentTree {
public:
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>>>dat;
vector<bool> used; vector<int> cl, cr;
int size_ = 1;
void init(int sz) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2);
}
void add_(int l, int r, int a, int b, int x, int u) {
if (l <= a && b <= r) { dat[u].push(make_pair(x, used.size())); return; }
if (r <= a || b <= l) return;
add_(l, r, a, (a + b) >> 1, x, u * 2);
add_(l, r, (a + b) >> 1, b, x, u * 2 + 1);
}
int add(int l, int r, int x) {
add_(l, r, 0, size_, x, 1);
used.push_back(false); cl.push_back(l); cr.push_back(r);
return used.size() - 1;
}
void query(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) {
while (!dat[u].empty()) {
int t = dat[u].top().second;
if (used[t] == true) dat[u].pop();
else break;
}
return;
}
if (r <= a || b <= l) return;
query(l, r, a, (a + b) >> 1, u * 2);
query(l, r, (a + b) >> 1, b, u * 2 + 1);
}
void dels(int num) {
used[num] = true;
query(cl[num], cr[num], 0, size_, 1);
}
int answer(int pos) {
pos += size_; int ans = -(1 << 30);
while (pos >= 1) {
if (!dat[pos].empty()) ans = max(ans, dat[pos].top().first);
pos >>= 1;
}
return ans;
}
};
const int MAX_N = (1 << 17);
int N, K, Q, R, X[MAX_N], T[MAX_N], A[MAX_N], B[MAX_N], L[MAX_N], Y[MAX_N], Answer[MAX_N], cnt1[MAX_N], cnt;
set<pair<int, int>> dishes[MAX_N]; map<tuple<int, int, int>, int>Map;
SegmentTree V1, V2; vector<int>VX; vector<tuple<int, int, int>>vec;
void delete_vision(int cl, int cr) {
if (R == 1) return;
if (cr != -2) V1.dels(Map[make_tuple(cl, cr, 1)]);
if (cl != -1) V2.dels(Map[make_tuple(cl, cr, 2)]);
}
void add_vision(int cl, int cr) {
if (R == 1) {
if (cl != -1 && cr != -2) VX.push_back((X[cl] + X[cr]) / 2);
return;
}
if (cl != -1 && cr != -2) {
int pos1 = lower_bound(VX.begin(), VX.end(), X[cl]) - VX.begin();
int pos2 = lower_bound(VX.begin(), VX.end(), (X[cl] + X[cr]) / 2) - VX.begin();
int pos3 = lower_bound(VX.begin(), VX.end(), X[cr]) - VX.begin();
int Z1 = V1.add(pos2, pos3 + 1, X[cr]); Map[make_tuple(cl, cr, 1)] = Z1;
int Z2 = V2.add(pos1, pos2 + 1, -X[cl]); Map[make_tuple(cl, cr, 2)] = Z2;
}
else if (cr != -2) {
int pos1 = lower_bound(VX.begin(), VX.end(), X[cr]) - VX.begin();
int Z1 = V1.add(0, pos1 + 1, X[cr]); Map[make_tuple(cl, cr, 1)] = Z1;
}
else if (cl != -1) {
int pos1 = lower_bound(VX.begin(), VX.end(), X[cl]) - VX.begin();
int Z2 = V2.add(pos1, VX.size() + 1, -X[cl]); Map[make_tuple(cl, cr, 2)] = Z2;
}
}
void delete_relation(int ty, int pos) {
if (ty == 1) {
// 2 点の場合
auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }
delete_vision(P1, P2);
}
if (ty == 2) {
auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos + 1));
int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }
delete_vision(P1, pos);
delete_vision(pos, P2);
}
}
void add_relation(int ty, int pos) {
if (ty == 1) {
// 3 点の場合
auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos + 1));
int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }
add_vision(P1, pos);
add_vision(pos, P2);
}
if (ty == 2) {
// 2 点の場合
auto itr1 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
auto itr2 = dishes[T[pos]].lower_bound(make_pair(X[pos], pos));
int P1 = -1; if (itr1 != dishes[T[pos]].begin()) { itr1--; P1 = (*itr1).second; }
int P2 = -2; if (itr2 != dishes[T[pos]].end()) { P2 = (*itr2).second; }
add_vision(P1, P2);
}
}
void add(int pos) {
cnt1[T[pos]]++; if (cnt1[T[pos]] == 1) cnt++;
delete_relation(1, pos);
dishes[T[pos]].insert(make_pair(X[pos], pos));
add_relation(1, pos);
}
void lose(int pos) {
cnt1[T[pos]]--; if (cnt1[T[pos]] == 0) cnt--;
delete_relation(2, pos);
dishes[T[pos]].erase(make_pair(X[pos], pos));
add_relation(2, pos);
}
int getval(int pos) {
int pos1 = lower_bound(VX.begin(), VX.end(), pos) - VX.begin();
int val1 = V1.answer(pos1) - pos;
int pos2 = lower_bound(VX.begin(), VX.end(), pos) - VX.begin();
int val2 = V2.answer(pos2) + pos;
return max(val1, val2);
}
set<int>Set[MAX_N];
int main() {
scanf("%d%d%d", &N, &K, &Q);
for (int i = 1; i <= N; i++) { scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); vec.push_back(make_tuple(A[i], 1, i)); vec.push_back(make_tuple(B[i], 3, i)); X[i] *= 2; }
for (int i = 1; i <= Q; i++) { scanf("%d%d", &L[i], &Y[i]); L[i] *= 2; vec.push_back(make_tuple(Y[i], 2, i)); }
for (int i = 1; i <= N; i++) VX.push_back(X[i]);
for (int i = 1; i <= Q; i++) VX.push_back(L[i]);
V1.init(VX.size() + 2);
V2.init(VX.size() + 2);
sort(vec.begin(), vec.end());
sort(VX.begin(), VX.end());
// まず 1 回シミュレーションを行う
R = 1;
for (int i = 0; i < vec.size(); i++) {
if (get<1>(vec[i]) == 1) {
add(get<2>(vec[i]));
}
if (get<1>(vec[i]) == 3) {
lose(get<2>(vec[i]));
}
}
sort(VX.begin(), VX.end());
VX.erase(unique(VX.begin(), VX.end()), VX.end());
// 次に、本シミュレーション
R = 2;
for (int i = 0; i < vec.size(); i++) {
if (get<1>(vec[i]) == 1) {
add(get<2>(vec[i]));
}
if (get<1>(vec[i]) == 2) {
Answer[get<2>(vec[i])] = getval(L[get<2>(vec[i])]);
if (cnt != K) Answer[get<2>(vec[i])] = -2;
}
if (get<1>(vec[i]) == 3) {
lose(get<2>(vec[i]));
}
}
for (int i = 1; i <= Q; i++) printf("%d\n", Answer[i] / 2);
return 0;
}
Compilation message
new_home.cpp:10:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
new_home.cpp: In function 'int main()':
new_home.cpp:191:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
new_home.cpp:206:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) {
~~^~~~~~~~~~~~
new_home.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &K, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:178:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= N; i++) { scanf("%d%d%d%d", &X[i], &T[i], &A[i], &B[i]); vec.push_back(make_tuple(A[i], 1, i)); vec.push_back(make_tuple(B[i], 3, i)); X[i] *= 2; }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:179:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= Q; i++) { scanf("%d%d", &L[i], &Y[i]); L[i] *= 2; vec.push_back(make_tuple(Y[i], 2, i)); }
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12672 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12672 KB |
Output is correct |
| 4 |
Runtime error |
33 ms |
25216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12672 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12672 KB |
Output is correct |
| 4 |
Runtime error |
33 ms |
25216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
85 ms |
20964 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
90 ms |
20940 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12672 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12672 KB |
Output is correct |
| 4 |
Runtime error |
33 ms |
25216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
16 ms |
12672 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12672 KB |
Output is correct |
| 4 |
Runtime error |
33 ms |
25216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
