CF76F. Tourist

제목 링크: CF76F. Tourist
엄 청 난 문제!!!
제목 대의: 하나의 수축 과 n (n < = 10 ^ 5) 사건 을 제시 합 니 다. 모든 사건 에 (xi, ti) 는 i 번 째 사건 이 위치 xi 에서 사건 ti 시간 에 발생 한 다 는 것 을 나타 내 고 V 는 이 사람의 속 도 를 1s 에서 최대 V 단위 의 길 이 를 걸 을 수 있다 는 것 을 나타 냅 니 다.1. 이 사람 이 0 자리 0 시 에 출발 하면 최대 몇 개의 사건 을 볼 수 있 는 지 물 어 본다.2 。이 사람 은 어느 위치 에서 든 0 시 에 출발 하면 얼마나 많은 사건 을 볼 수 있 습 니까?
사고: 이 문 제 를 받 기 시 작 했 을 때 첫 번 째 생각 은 모든 사건 을 사건 ti 로 정렬 한 다음 에 가방 과 같은 사고 로 이 문 제 를 푸 는 것 이 었 다. 그러면 사건 의 재 검 도 는 O (n ^ 2), dp [(x [i], t [i]]] = max (dp [j], t [j]), j & i & & &  | x[i]-x[j]  | <= V * (ti - tj), 그리고 데이터 구조 로 상태 전 이 를 최적화 할 생각 을 했 는데 | x [i] - x [j]  | <= V * (ti - tj) 의 제한 조건 은 거의 최적화 되 지 않 고 그 다음 에 해 낼 수 없다.
            문제 보고 보기 | x [i] - x [j]  | <= V*(ti - tj)  이 부등식 은 두 개의 부등식 으로 나 눌 수 있다.  V*t[i] + x[i ]  >= V*t[j] + x[j]   2. V*t[i] - x[i]  >= V*t[j] - x[j]  ,그리고 모든 사건 이 2 차원 좌표 로 비 치 는 것 을 신기 하 게 발견 했다 (V * t [i]  + x[i]  , V*t[i ]  - x[i] ) ,그 다음 에 LIS 의 최 장 상승 서브 시퀀스 문제 입 니 다. 이 문 제 를 생각하면 거의 완성 되 지 않 았 습 니 다.
          결합 문제: 첫 번 째 질문 은 최초의 상태 가 (0, 0) 여야 한다 고 요구 합 니 다. 그러면 매 핑 된 좌 표 는 첫 번 째 상한 점 만 갈 수 있 음 을 자세히 분석 한 결과
                              두 번 째 질문 은 시작 점 에 대한 요구 가 없 으 니 마음대로 해도 된다.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <set>

using namespace std;

const int maxn=201000;
typedef long long ll;
struct Point
{
    ll x,y;
    bool operator<(Point a)const
    {
        if(x!=a.x) return x < a.x;
        return y < a.y;
    }
}p[maxn];
int x[maxn],t[maxn];

int LIS(int n)
{
    multiset<ll> st;
    multiset<ll>::iterator it;
    for(int i=0;i<n;i++)
    {
        it=st.upper_bound(p[i].y);
        if(it!=st.end()) st.erase(it);
        st.insert(p[i].y);
    }
    return st.size();
}
int main()
{
    int n;
    long long V;
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<n;i++) scanf("%d%d",&x[i],&t[i]);
        scanf("%I64d",&V);
        int tot=0;
        for(int i=0;i<n;i++)
          if(V*t[i]+x[i]>=0&&V*t[i]-x[i]>=0)
          {
              p[tot].x=V*t[i]+x[i];
              p[tot++].y=V*t[i]-x[i];
          }
        sort(p,p+tot);
       /* for(int i=0;i<tot;i++)
          cout<<p[i].x<<" "<<p[i].y<<endl;*/
        int ans1=LIS(tot);
        for(int i=0;i<n;i++)
          {
              p[i].x=V*t[i]+x[i];
              p[i].y=V*t[i]-x[i];
          }
        sort(p,p+n);
        int ans2=LIS(n);
        printf("%d %d
",ans1,ans2);
    }
    return 0;
}