bool home = 0;
#include <bits/stdc++.h>
using namespace std;
struct Store {
int x;
int type;
int first_time;
int last_time;
};
struct Query {
int x;
int t;
};
const int N = (int) 3e5 + 7;
int n;
int k;
int q;
vector<int> whereType[N];
Store stores[N];
Query queries[N];
bool negative[N];
vector<int> events;
int getTimeOfEvent(int i) {
if (i >= 1) {
assert(1 <= i && i <= n);
return stores[i].first_time;
} else {
i *= -1;
assert(1 <= i && i <= n);
return stores[i].last_time + 1;
}
}
bool cmpEvents(int i, int j) {
return getTimeOfEvent(i) < getTimeOfEvent(j);
}
struct Position {
int i;
};
bool operator < (Position a, Position b) {
int i = a.i, j = b.i;
if (stores[i].x == stores[j].x) {
return i < j;
} else {
return stores[i].x < stores[j].x;
}
}
struct Segment {
int first_time;
int last_time;
int x1;
int x2;
};
struct RelaxSegment {
int first_time;
int last_time;
int limit;
int x;
};
vector<RelaxSegment> rels[2];
vector<Segment> segments;
void addSegment(int first_time, int last_time, int i, int j) {
assert(1 <= i && i <= n + 2);
assert(1 <= j && j <= n + 2);
if (first_time > last_time) {
return;
}
assert(0 <= first_time && first_time <= last_time && last_time < q);
assert(stores[i].x <= stores[j].x);
segments.push_back({first_time, last_time, stores[i].x, stores[j].x});
}
int print[N];
int main() {
if (home) {
freopen ("input.txt", "r", stdin);
} else {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
{
/// Read
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
cin >> stores[i].x >> stores[i].type >> stores[i].first_time >> stores[i].last_time;
}
for (int i = 1; i <= q; i++) {
cin >> queries[i].x >> queries[i].t;
}
}
{
/// Normalize time
vector<int> interestingTimes;
for (int i = 1; i <= q; i++) {
interestingTimes.push_back(queries[i].t);
}
sort(interestingTimes.begin(), interestingTimes.end());
interestingTimes.resize(unique(interestingTimes.begin(), interestingTimes.end()) - interestingTimes.begin());
for (int i = 1; i <= q; i++) {
queries[i].t = lower_bound(interestingTimes.begin(), interestingTimes.end(), queries[i].t) - interestingTimes.begin();
}
int y = 0;
for (int i = 1; i <= n; i++) {
stores[i].first_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].first_time) - interestingTimes.begin();
stores[i].last_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].last_time + 1) - interestingTimes.begin() - 1;
if (stores[i].first_time <= stores[i].last_time) {
stores[++y] = stores[i];
}
}
n = y;
}
{
/// Some more computation
for (int i = 1; i <= n; i++) {
whereType[stores[i].type].push_back(i);
}
stores[n + 1].x = -((int) 1e8 + 7);
stores[n + 2].x = +((int) 2e8 + 7);
for (int type = 1; type <= k; type++) {
set<Position> positions;
map<pair<int, int>, int> sinceWhen;
positions.insert({n + 1});
positions.insert({n + 2});
sinceWhen[{n + 1, n + 2}] = 0;
events.clear();
for (auto &i : whereType[type]) {
events.push_back(+i);
events.push_back(-i);
}
sort(events.begin(), events.end(), cmpEvents);
int l_events = 0;
while (l_events < (int) events.size()) {
int r_events = l_events;
while (r_events + 1 < (int) events.size() && getTimeOfEvent(events[r_events + 1]) == getTimeOfEvent(events[r_events])) {
r_events++;
}
int current_time = getTimeOfEvent(events[l_events]);
for (int iter_events = l_events; iter_events <= r_events; iter_events++) {
int i = events[iter_events];
if (i >= 1) {
assert(1 <= i && i <= n);
positions.insert({i});
auto it = positions.find({i});
assert(it != positions.end());
auto nxt = it;
auto ant = it;
nxt++;
assert(nxt != positions.end());
assert(ant != positions.begin());
ant--;
addSegment(sinceWhen[{ant->i, nxt->i}], current_time - 1, ant->i, nxt->i);
assert(sinceWhen.count({ant->i, nxt->i}));
sinceWhen.erase({ant->i, nxt->i});
assert(!sinceWhen.count({ant->i, nxt->i}));
sinceWhen[{ant->i, it->i}] = current_time;
sinceWhen[{it->i, nxt->i}] = current_time;
} else {
i *= -1;
assert(1 <= i && i <= n);
assert(positions.count({i}));
auto it = positions.find({i});
assert(it != positions.end());
auto nxt = it;
auto ant = it;
nxt++;
assert(nxt != positions.end());
assert(ant != positions.begin());
ant--;
assert(!sinceWhen.count({ant->i, nxt->i}));
sinceWhen[{ant->i, nxt->i}] = current_time;
assert(sinceWhen.count({ant->i, nxt->i}));
addSegment(sinceWhen[{ant->i, it->i}], current_time - 1, ant->i, it->i);
assert(sinceWhen.count({ant->i, it->i}));
sinceWhen.erase({ant->i, it->i});
addSegment(sinceWhen[{it->i, nxt->i}], current_time - 1, it->i, nxt->i);
assert(sinceWhen.count({it->i, nxt->i}));
sinceWhen.erase({it->i, nxt->i});
positions.erase({i});
}
}
l_events = r_events + 1;
}
for (auto &it : sinceWhen) {
addSegment(it.second, q - 1, it.first.first, it.first.second);
}
}
}
{
/// Some other Brute
for (auto &segment : segments) {
int t1 = segment.first_time;
int t2 = segment.last_time;
int x1 = segment.x1;
int x2 = segment.x2;
int xmid = (x1 + x2) / 2;
rels[0].push_back({t1, t2, xmid, x1});
rels[1].push_back({t1, t2, -xmid, -x2});
}
for (int inv = 0; inv <= 1; inv++) {
vector<RelaxSegment> relaxSegments = rels[inv];
for (int iq = 1; iq <= q; iq++) {
for (auto &relaxSegment : relaxSegments) {
if (relaxSegment.first_time <= queries[iq].t && queries[iq].t <= relaxSegment.last_time) {
if (queries[iq].x <= relaxSegment.limit) {
print[iq] = max(print[iq], queries[iq].x - relaxSegment.x);
}
}
}
}
for (int iq = 1; iq <= q; iq++) {
queries[iq].x *= -1;
}
}
for (int iq = 1; iq <= q; iq++) {
int maxDist = 0;
for (auto &segment : segments) {
if (segment.first_time <= queries[iq].t && queries[iq].t <= segment.last_time) {
if (segment.x1 <= queries[iq].x && queries[iq].x <= segment.x2) {
maxDist = max(maxDist, min(abs(queries[iq].x - segment.x1), abs(queries[iq].x - segment.x2)));
}
}
}
assert(maxDist == print[iq]);
if (maxDist > (int) 1e8) {
maxDist = -1;
}
cout << maxDist << "\n";
}
return 0;
cout << " ----------- \n";
}
{
/// Brute
for (int iq = 1; iq <= q; iq++) {
int maxDist = 0;
for (int t = 1; t <= k; t++) {
int minDist = (int) 1e9 + 7;
for (auto &i : whereType[t]) {
if (stores[i].first_time <= queries[iq].t && queries[iq].t <= stores[i].last_time) {
minDist = min(minDist, abs(stores[i].x - queries[iq].x));
}
}
maxDist = max(maxDist, minDist);
}
if (maxDist == (int) 1e9 + 7) {
maxDist = -1;
}
cout << maxDist << "\n";
}
}
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen ("input.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7328 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 5 |
Runtime error |
11 ms |
14972 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7328 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 5 |
Runtime error |
11 ms |
14972 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
50864 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5071 ms |
64092 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7328 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 5 |
Runtime error |
11 ms |
14972 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7328 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7280 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7380 KB |
Output is correct |
| 5 |
Runtime error |
11 ms |
14972 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
