Submission #986718

#	Time	Username	Problem	Language	Result	Execution time	Memory
986718		_callmelucian	Advertisement 2 (JOI23_ho_t2)	C++14	10 / 100	391 ms	37644 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<int> tr;
    IT (int sz) : tr(4 * sz, INT_MIN) {}

    void update (int pos, int val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) {
            tr[k] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = max(tr[2 * k], tr[2 * k + 1]);
    }

    int walk (int k, int l, int r, int ub) {
        if (l == r) return (tr[k] <= ub ? l : INT_MAX);
        int mid = (l + r) >> 1;
        if (tr[2 * k + 1] <= ub)
            return min(walk(2 * k, l, mid, ub), mid + 1);
        return walk(2 * k + 1, mid + 1, r, ub);
    }
};

struct simpleIT {
    vector<int> tr;
    simpleIT (int sz) : tr(4 * sz, INT_MAX) {}

    void update (int pos, int val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) {
            tr[k] = min(tr[k], val);
            return;
        }
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = min(tr[2 * k], tr[2 * k + 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return INT_MAX;
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return min(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
};

const int mn = 5e5 + 5;

struct resident {
    int X, E;

    resident() : X(0), E(0) {}
    resident (int _x, int _e) : X(_x), E(_e) {}

    friend istream& operator >> (istream &inp, resident &r) {
        inp >> r.X >> r.E;
        return inp;
    }

    bool operator < (const resident &o) const {
        //if (E == o.E) return X < o.X;
        //return E < o.E;
        return max(E + X, E - X) < max(o.E + o.X, o.E - o.X);
    }
} res[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> res[i];
    sort(res + 1, res + 1 + n);

    /*cout << "after sort\n";
    for (int i = 1; i <= n; i++) {
        cout << res[i].X << " " << res[i].E << "\n";
    }*/

    simpleIT dp(n + 1); IT trSum(n), trDif(n);
    dp.update(0, 0, 1, 0, n);

    for (int i = 1; i <= n; i++) {
        int lb = max(trSum.walk(1, 1, n, res[i].E + res[i].X), trDif.walk(1, 1, n, res[i].E - res[i].X));
        int cur = dp.query(lb - 1, i - 1, 1, 0, n) + 1;
        trSum.update(i, res[i].E + res[i].X, 1, 1, n);
        trDif.update(i, res[i].E - res[i].X, 1, 1, n);
        dp.update(i, cur, 1, 0, n);
        //cout << "dp " << i << ": " << cur << "\n";
    }
    cout << dp.query(n, n, 1, 0, n);

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 23
• Subtask 3: 0 / 36
• Subtask 4: 0 / 31