| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 400174 |
2021-05-07T13:38:40 Z |
tmbao |
New Home (APIO18_new_home) |
C++14 |
|
1248 ms |
421468 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
enum EventType {
ADD, REMOVE,
};
struct Event {
int pos, store, time;
EventType type;
};
struct Query {
int index, pos, time;
};
struct SegmentTree {
string name;
int size;
vector<multiset<int>> data;
void resize(int _size) {
data.resize(_size * 3);
size = _size;
}
void addInternal(int i, int u, int v, int l, int r, int val) {
if (v < l || r < u) {
return;
}
if (l <= u && v <= r) {
data[i].insert(val);
return;
}
int mid = (u + v) / 2;
addInternal(i * 2, u, mid, l, r, val);
addInternal(i * 2 + 1, mid + 1, v, l, r, val);
}
void removeInternal(int i, int u, int v, int l, int r, int val) {
if (v < l || r < u) {
return;
}
if (l <= u && v <= r) {
data[i].erase(data[i].find(val));
return;
}
propagate(i, val);
int mid = (u + v) / 2;
removeInternal(i * 2, u, mid, l, r, val);
removeInternal(i * 2 + 1, mid + 1, v, l, r, val);
}
void add(int l, int r, int val) {
// cout << name << "+" << l << " " << r << " " << val << endl;
addInternal(1, 1, size, l + 1, r + 1, val);
}
void remove(int l, int r, int val) {
// cout << name << "-" << l << " " << r << " " << val << endl;
removeInternal(1, 1, size, l + 1, r + 1, val);
}
int getMin(int u) {
// cout << "g " << u << endl;
return getMinInternal(1, 1, size, u + 1);
}
int getMax(int u) {
// cout << "g " << u << endl;
return getMaxInternal(1, 1, size, u + 1);
}
int getMinInternal(int i, int l, int r, int u) {
if (u < l || r < u) {
return INF;
}
int ret = INF;
if (data[i].size() > 0) {
ret = *data[i].begin();
}
if (l < r) {
int mid = (l + r) / 2;
ret = min(ret, getMinInternal(i * 2, l, mid, u));
ret = min(ret, getMinInternal(i * 2 + 1, mid + 1, r, u));
}
return ret;
}
int getMaxInternal(int i, int l, int r, int u) {
if (u < l || r < u) {
return -INF;
}
int ret = -INF;
if (data[i].size() > 0) {
ret = *data[i].rbegin();
}
if (l < r) {
int mid = (l + r) / 2;
ret = max(ret, getMaxInternal(i * 2, l, mid, u));
ret = max(ret, getMaxInternal(i * 2 + 1, mid + 1, r, u));
}
return ret;
}
void propagate(int i, int val) {
if (data[i].find(val) != data[i].end()) {
data[i * 2].insert(val);
data[i * 2 + 1].insert(val);
data[i].erase(data[i].find(val));
}
}
} segTreeMin, segTreeMax;
void removeSegment(int prev, int next, const vector<int>& allPositions) {
if (prev == -1 && next == allPositions.size()) {
return;
}
if (prev == -1) {
segTreeMax.remove(0, next, allPositions[next]);
return;
}
if (next == allPositions.size()) {
segTreeMin.remove(prev, allPositions.size() - 1, allPositions[prev]);
return;
}
int midVal = (allPositions[prev] + allPositions[next]) / 2;
int mid = distance(
allPositions.begin(), upper_bound(allPositions.begin(), allPositions.end(), midVal));
segTreeMin.remove(prev, mid - 1, allPositions[prev]);
segTreeMax.remove(mid, next, allPositions[next]);
}
void insertSegment(int prev, int next, const vector<int>& allPositions) {
if (prev == -1) {
segTreeMax.add(0, next, allPositions[next]);
return;
}
if (next == allPositions.size()) {
segTreeMin.add(prev, allPositions.size() - 1, allPositions[prev]);
return;
}
int midVal = (allPositions[prev] + allPositions[next]) / 2;
int mid = distance(
allPositions.begin(), upper_bound(allPositions.begin(), allPositions.end(), midVal));
segTreeMin.add(prev, mid - 1, allPositions[prev]);
segTreeMax.add(mid, next, allPositions[next]);
}
void insertPosition(int prev, int curr, int next, const vector<int>& allPositions) {
// cout << prev << " " << curr << " " << next << endl;
if (curr == allPositions.size() - 1 && prev <= 0) {
insertSegment(-1, curr, allPositions);
return;
}
if (curr == 0 && next >= allPositions.size() - 1) {
insertSegment(curr, allPositions.size(), allPositions);
return;
}
removeSegment(prev, next, allPositions);
insertSegment(prev, curr, allPositions);
insertSegment(curr, next, allPositions);
}
void removePosition(int prev, int curr, int next, const vector<int>& allPositions) {
removeSegment(prev, curr, allPositions);
removeSegment(curr, next, allPositions);
insertSegment(prev, next, allPositions);
}
bool cmpQuery(const Query& q1, const Query& q2) {
return q1.time < q2.time;
}
bool compEvent(const Event& e1, const Event& e2) {
return e1.time < e2.time;
}
int main() {
int n, q, k;
cin >> n >> k >> q;
vector<Event> events;
vector<Query> queries;
vector<int> allPositions;
for (int i = 0; i < n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
events.push_back({x, t - 1, a, EventType::ADD});
events.push_back({x, t - 1, b + 1, EventType::REMOVE});
allPositions.push_back(x);
}
for (int i = 0; i < q; ++i) {
int l, y;
cin >> l >> y;
queries.push_back({i, l, y});
allPositions.push_back(l);
}
allPositions.push_back(-INF);
allPositions.push_back(INF);
for (int i = 0; i < k; ++i) {
events.push_back({INF, i, 0, EventType::ADD});
events.push_back({-INF, i, 0, EventType::ADD});
}
// Compress pos
sort(allPositions.begin(), allPositions.end());
allPositions.resize(
distance(allPositions.begin(), unique(allPositions.begin(), allPositions.end())));
segTreeMin.resize(allPositions.size()); segTreeMin.name = "segTreeMin";
segTreeMax.resize(allPositions.size()); segTreeMax.name = "segTreeMax";
for (Event &event : events) {
event.pos = distance(
allPositions.begin(), lower_bound(allPositions.begin(), allPositions.end(), event.pos));
}
for (Query &query : queries) {
query.pos = distance(
allPositions.begin(), lower_bound(allPositions.begin(), allPositions.end(), query.pos));
}
sort(events.begin(), events.end(), compEvent);
sort(queries.begin(), queries.end(), cmpQuery);
vector<multiset<int>> storePos;
storePos.resize(k);
int noStoresAvailable = 0;
vector<int> answer;
answer.resize(q);
for (int i = 0, j = 0; i < queries.size(); ++i) {
Query query = queries[i];
for (; j < events.size() && events[j].time <= query.time; ++j) {
Event event = events[j];
switch (event.type) {
case ADD: {
if (storePos[event.store].size() == 2) {
noStoresAvailable++;
}
auto it = storePos[event.store].lower_bound(event.pos);
if (it == storePos[event.store].end() || (*it) != event.pos) {
int prevValue = -1;
if (it != storePos[event.store].end() && it != storePos[event.store].begin()) {
auto prevIt = prev(it);
prevValue = *prevIt;
}
int nextValue = allPositions.size();
auto nextIt = storePos[event.store].upper_bound(event.pos);
if (it != storePos[event.store].end() && nextIt != storePos[event.store].end()) {
nextValue = *nextIt;
}
insertPosition(prevValue, event.pos, nextValue, allPositions);
}
storePos[event.store].insert(event.pos);
break;
}
case REMOVE: {
if (storePos[event.store].size() == 3) {
noStoresAvailable--;
}
auto it = storePos[event.store].lower_bound(event.pos);
if (next(it) != storePos[event.store].end() && (*next(it)) != (*it)) {
int prevValue = -1;
if (it != storePos[event.store].begin()) {
auto prevIt = prev(it);
prevValue = *prevIt;
}
int nextValue = allPositions.size();
auto nextIt = storePos[event.store].upper_bound(event.pos);
if (nextIt != storePos[event.store].end()) {
nextValue = *nextIt;
}
removePosition(prevValue, event.pos, nextValue, allPositions);
}
storePos[event.store].erase(it);
break;
}
}
}
if (noStoresAvailable < k) {
answer[query.index] = -1;
} else {
int left = segTreeMin.getMin(query.pos);
int right = segTreeMax.getMax(query.pos);
int result = min(allPositions[query.pos] - left, right - allPositions[query.pos]);
answer[query.index] = result;
}
}
for (int i = 0; i < q; ++i) {
cout << answer[i] << endl;
}
return 0;
}
Compilation message
new_home.cpp: In function 'void removeSegment(int, int, const std::vector<int>&)':
new_home.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | if (prev == -1 && next == allPositions.size()) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:125:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if (next == allPositions.size()) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void insertSegment(int, int, const std::vector<int>&)':
new_home.cpp:141:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | if (next == allPositions.size()) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void insertPosition(int, int, int, const std::vector<int>&)':
new_home.cpp:154:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | if (curr == allPositions.size() - 1 && prev <= 0) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:158:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | if (curr == 0 && next >= allPositions.size() - 1) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:238:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
238 | for (int i = 0, j = 0; i < queries.size(); ++i) {
| ~~^~~~~~~~~~~~~~~~
new_home.cpp:240:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
240 | for (; j < events.size() && events[j].time <= query.time; ++j) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1248 ms |
421468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1209 ms |
404400 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
