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>
using namespace std;
const int NMAX = 2e5 + 1, QMAX = 2e5 + 1;
const int TMAX = (NMAX + QMAX - 1);
typedef pair < int, int > PII;
typedef pair < int, PII > PIII;
int N, Q;
PII A[NMAX];
PIII Queries[QMAX];
int B[(TMAX << 1)], V[(TMAX << 1)];
int dp[NMAX], Best[(TMAX << 1)];
int ans[QMAX];
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
for(int i = 1; i <= N; ++i)
{
cin >> A[i].first >> A[i].second;
B[++B[0]] = A[i].first, B[++B[0]] = A[i].second;
}
for(int i = 1; i <= Q; ++i)
{
cin >> Queries[i].second.first >> Queries[i].second.second, Queries[i].first = i;
B[++B[0]] = Queries[i].second.first, B[++B[0]] = Queries[i].second.second;
}
return;
}
static inline int Find (int Val)
{
return (int)(lower_bound(V + 1, V + V[0] + 1, Val) - V);
}
static inline void Replace ()
{
for(int i = 1; i <= N; ++i)
A[i].first = Find(A[i].first), A[i].second = Find(A[i].second);
for(int i = 1; i <= Q; ++i)
Queries[i].second.first = Find(Queries[i].second.first), Queries[i].second.second = Find(Queries[i].second.second);
return;
}
static inline void Normalize ()
{
sort(B + 1, B + B[0] + 1);
V[++V[0]] = B[1];
for(int i = 2; i <= B[0]; ++i)
if(B[i] != B[i - 1])
V[++V[0]] = B[i];
Replace();
return;
}
auto cmp_1 = [] (PII A, PII B)
{
if(A.second < B.second)
return 1;
if(A.second > B.second)
return 0;
if(A.first > B.first)
return 1;
return 0;
};
auto cmp_2 = [] (PIII A, PIII B)
{
if(A.second.second < B.second.second)
return 1;
return 0;
};
static inline void Sort ()
{
sort(A + 1, A + N + 1, cmp_1);
sort(Queries + 1, Queries + Q + 1, cmp_2);
return;
}
static inline int my_max (int a, int b)
{
return ((a > b) ? a : b);
}
static inline void Solve ()
{
int Last_Valid_Position = 0;
for(int p = 1; p <= Q; ++p)
{
int copy = Last_Valid_Position;
while(Last_Valid_Position < N && A[Last_Valid_Position + 1].second <= Queries[p].second.second)
++Last_Valid_Position;
for(int i = (copy + 1); i <= Last_Valid_Position; ++i)
{
dp[i] = 1;
for(int j = (i - 1); j >= 1; --j)
if(A[j].first >= A[i].first)
dp[i] = my_max(dp[i], dp[j] + 1);
dp[i] = my_max(dp[i], Best[A[i].second] + 1);
Best[A[i].second] = my_max(Best[A[i].second], dp[i]);
}
int Max = 0;
for(int i = 1; i <= Last_Valid_Position; ++i)
if(A[i].first >= Queries[p].second.first)
Max = my_max(Max, dp[i]);
ans[Queries[p].first] = Max;
}
return;
}
static inline void Write ()
{
for(int i = 1; i <= Q; ++i)
cout << ans[i] << '\n';
return;
}
int main()
{
Read();
Normalize();
Sort();
Solve();
Write();
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... |