#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 2e5+5;
vector<int> G;
vector<int> H;
signed main()
{
fast();
int n, q;
cin >> n >> q;
vector<pair<in, int>> Q(q);
vector<in> RH(n+1);
RH[0] = {-INF, -1};
for(int i = 1; i <= n; i++)
{
cin >> RH[i].f >> RH[i].s;
RH[i].f = -RH[i].f;
G.pb(RH[i].f);
}
for(int i = 0; i < q; i++)
{
Q[i].s = i;
cin >> Q[i].f.f >> Q[i].f.s;
Q[i].f.f = -Q[i].f.f;
G.pb(Q[i].f.f);
}
sort(RH.begin(), RH.end());
sort(G.begin(), G.end());
H.pb(G[0]);
for(auto x: G)
{
if(x != H.back())
H.pb(x);
}
G.clear();
for(auto &[u, v]: RH)
{
u = lower_bound(H.begin(), H.end(), u)-H.begin()+1;
G.pb(v);
}
for(auto &[qq, i]: Q)
{
qq.f = lower_bound(H.begin(), H.end(), qq.f)-H.begin()+1;
G.pb(qq.s);
}
H.clear();
sort(G.begin(), G.end());
H.pb(G[0]);
for(auto x: G)
{
if(x != H.back())
H.pb(x);
}
for(auto &[u, v]: RH)
v = lower_bound(H.begin(), H.end(), v)-H.begin()+1;
for(auto &[qq, i]: Q)
qq.s = lower_bound(H.begin(), H.end(), qq.s)-H.begin()+1;
sort(Q.begin(), Q.end());
cout << "Printing RH values" << endl;
for(auto [u, v]: RH)
cout << u << " " << v << endl;
int r = 1;
vector<int> ans(q, 0);
vector<in> d(n+1, {INF, INF});
d[0] = {-INF, -INF};
for(int i = 0; i < q; i++)
{
int x = Q[i].s;
while((r <= n) && (RH[r].f <= Q[i].f.f))
{
//add RH[r].s
//RH[r].s can provide
in pp = {RH[r].s, r};
int W = upper_bound(d.begin(), d.end(), pp) - d.begin();
if((d[W-1] < pp) && (pp < d[W]))
d[W] = pp;
r++;
}
in ok = {Q[i].f.s, INF};
ans[x] = upper_bound(d.begin(), d.end(), ok)-d.begin()-1;
}
for(int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
