#pragma GCC optimize("O3")
#include <bits/stdc++.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: In function 'void linesweep(std::vector<std::pair<int, int> >&, std::vector<bool>&, std::vector<int>&, int)':
robots.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | for (int i = 0; i < points.size(); ++i)
| ~~^~~~~~~~~~~~~~~
robots.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for (int i = 0; i < as.size(); ++i)
| ~~^~~~~~~~~~~
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status
