#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
void linesweep(vector<pair<int, int>> &points, vector<bool> &marc, vector<int> &as, int k) {
vector<tuple<int, int, int>> events;
for (int i = 0; i < points.size(); ++i)
events.emplace_back(points[i].first, points[i].second, i);
for (int i = 0; i < as.size(); ++i)
events.emplace_back(as[i], 2e9, i);
sort(events.begin(), events.end());
set<pair<int, int>> toys;
for (auto [x, y, idx]: events) {
// cerr << "PROCESSING " << x << " " << y << " " << idx << "\n";
if (y < 1e9 && !marc[idx]) toys.emplace(y, idx);
else if (y == 2e9)
for (int i = 0; i < k && !toys.empty(); ++i) {
// cerr << idx << " TOOK TOY " << toys.rbegin()->second << "\n";
marc[toys.rbegin()->second] = true;
toys.erase(--toys.end());
}
}
// cerr << "FINISH PART\n";
}
bool check(vector<pair<int, int>> &points, vector<int> &as, vector<int> &bs, int k) {
vector<pair<int, int>> stniop;
for (auto [x, y]: points)
stniop.emplace_back(y, x);
vector<bool> marc(points.size());
linesweep(points, marc, as, k);
linesweep(stniop, marc, bs, k);
// cerr << "ANSWER: " << k << " ";
for (bool b: marc)
if (!b) {
// cerr << "NO\n";
return false;
}
// cerr << "YES\n";
return true;
}
int putaway(int a, int b, int t, int as[], int bs[], int xs[], int ys[]) {
vector<pair<int, int>> points;
for (int i = 0; i < t; ++i)
points.emplace_back(xs[i], ys[i]);
vector<int> xlines, ylines;
for (int i = 0; i < a; ++i)
xlines.push_back(as[i]-1);
for (int i = 0; i < b; ++i)
ylines.push_back(bs[i]-1);
xlines.push_back(0);
ylines.push_back(0);
sort(xlines.begin(), xlines.end());
sort(ylines.begin(), ylines.end());
for (auto [x, y]: points)
if (x > xlines.back() && y > ylines.back()) return -1;
int l = 0, r = t;
while (l < r-1) {
cerr << l << " " << r << "\n";
int m = (l + r)/2;
if (check(points, xlines, ylines, m)) r = m;
else l = m;
}
return r;
}
Compilation message
robots.cpp:3:10: fatal error: robots.h: No such file or directory
3 | #include "robots.h"
| ^~~~~~~~~~
compilation terminated.
