CFGYM104017C

Il Derby della Madonnina

题意

裁判在一条直线上，在第$t_i$时，他走到$a_i$点，他获得一分，起始，裁判在0号点，最大速度为v，求其能得几分。

题解

$|a_i-a_j|\le v*(t_i-t_j)$时，裁判可以从$j$号点转移到$i$号点。即

$a_i-a_j \le v*(t_i-t_j) $且$a_i-a_j\ge -v*(t_i-t_j)$时可以转移，移项得到：

$a_i-v*t_i\le a_j-v*t_j$且$a_i+v*t_i\ge a_j+v*t_j$时才可转移，记$l_i=a_i-v*t_i$,$r_i= a_i+v*t_i$，那么当

$l_i\le l_j$,$r_i\ge r_j$时可以转移，那么问题转化为了有多少个(l,r)套在一起，用线段树可以维护。

代码

//
// Created by mrx on 2023/4/9.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;


struct Nod {
    i64 max;
    
    Nod() : max(0) {}
    
    Nod(int x) {
        max = x;
    }
    
    //根据需要改变
    friend Nod merge(const Nod& lhs, const Nod& rhs) {
        Nod ans;
        ans.max = std::max(lhs.max, rhs.max);
        return ans;
    }
    
};


struct SegmentTree {
    std::vector<Nod> tree;
    int n;
    
    inline void push_up(int rt) {
        tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1]);
    }
    
    template<typename M>
    void build(int l, int r, int rt, const std::vector<M>& base) {
        if (l == r) {
            tree[rt] = base[l];
            return;
        }
        int m = (l + r) >> 1;
        build(l, m, rt << 1, base);
        build(m + 1, r, rt << 1 | 1, base);
        push_up(rt);
    }
    
    template<typename M>
    void _modify(int l, int r, int L, int R, int rt, const M& v) {
        if (L <= l && r <= R) {
            tree[rt] = v;
            return;
        }
        int m = (l + r) >> 1;
        if (L <= m)_modify(l, m, L, R, rt << 1, v);
        if (R > m)_modify(m + 1, r, L, R, rt << 1 | 1, v);
        push_up(rt);
    }
    
    Nod qry(int l, int r, int L, int R, int rt) {
        if (L <= l && r <= R) {
            return tree[rt];
        }
        int m = (l + r) >> 1;
        Nod res;
        if (R <= m)res = qry(l, m, L, R, rt << 1);
        else if (L > m)res = qry(m + 1, r, L, R, rt << 1 | 1);
        else res = merge(qry(l, m, L, R, rt << 1), qry(m + 1, r, L, R, rt << 1 | 1));
        push_up(rt);
        return res;
    }
    
    template<class Type>
    SegmentTree(const std::vector<Type>& a) {
        n = a.size();
        n--;
        tree.resize((n << 2) + 1);
        build(1, n, 1, a);
    }
    
    template<typename M>
    void modify(int L, int R, const M& v) {
        _modify(1, n, L, R, 1, v);
    }
    
    Nod query(int L, int R) {
        return qry(1, n, L, R, 1);
    }
    
    Nod query(int pos) {
        return qry(1, n, pos, pos, 1);
    }
};


void solve() {
    int n, v;
    std::cin >> n >> v;
    std::vector<i64> a(n), t(n);
    for (int i = 0; i < n; ++i)std::cin >> t[i];
    for (int i = 0; i < n; ++i)std::cin >> a[i];
    std::vector<std::pair<i64, i64>> lr;
    for (int i = 0; i < n; ++i) {
        i64 l = a[i] - v * t[i], r = a[i] + v * t[i];
        if (l <= 0 && r >= 0)lr.emplace_back(l, r);
    }
    lr.emplace_back(0, 0);
    std::vector<i64> lsh;
    for (auto& [l, r]: lr) {
        lsh.push_back(l);
        lsh.push_back(r);
    }
    std::sort(lsh.begin(), lsh.end());
    lsh.erase(std::unique(lsh.begin(), lsh.end()), lsh.end());
    for (auto& [l, r]: lr) {
        l = std::lower_bound(lsh.begin(), lsh.end(), l) - lsh.begin() + 1;
        r = std::lower_bound(lsh.begin(), lsh.end(), r) - lsh.begin() + 1;
    }
    SegmentTree Tree(std::vector<int>(lsh.size() + 2, 0));
    std::sort(lr.begin(), lr.end(), [](const auto& lhs, const auto& rhs) {
        return lhs.second == rhs.second ? lhs.first > rhs.first : lhs.second < rhs.second;
    });
    i64 ans = 0;
    for (auto [l, r]: lr) {
        auto tmp = Tree.query(l, r).max;
        tmp++;
        ans = std::max(ans, tmp);
        Tree.modify(l, l, tmp);
    }
    std::cout << ans - 1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}