This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <set>
#include <tuple>
#define pii pair<int, int>
#define fst first
#define snd second
/*
Observe that we can go from a pair to another pair iff:
|Aj - Ai| <= Tj - Ti
Therefore,
Ti - Ai <= Tj - Aj ---> if Ai <= Aj
Ti + Ai <= Tj + Aj ---> if Ai > Aj
Observe that if Ti - Ai <= Tj - Aj for Ai <= Aj
Ti + Ai <= Tj + Aj will also be satisfied.
Therefore, we could sort the array based on Ti - Ai
And change each element in the array into just Ti + Ai
And the problem is now reduced to :
The minimum number of groups required such that each group
is an non-decreasing subsequence of the array.
*/
using namespace std;
set<int> s;
int m, n;
pii ar[500001];
pii srt[500001];
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> m >> n;
for (int i = 0; i < n; i++) {cin >> ar[i].snd;}
for (int i = 0; i < n; i++)
{
cin >> ar[i].fst;
tie(ar[i].fst, ar[i].snd) = make_tuple(ar[i].snd - ar[i].fst, ar[i].fst + ar[i].snd);
}
sort(ar, ar + n);
for (int i = 0; i < n; i++)
{
srt[i] = {ar[i].snd, i};
}
sort(srt, srt + n);
for (int i = 0; i < n; i++)
{
auto it = s.lower_bound(srt[i].snd);
if (it != s.begin()) s.erase(prev(it));
s.insert(srt[i].snd);
}
cout << s.size() << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |