Submission #895930

#	Time	Username	Problem	Language	Result	Execution time	Memory
895930		frostray8653	Advertisement 2 (JOI23_ho_t2)	C++17	59 / 100	56 ms	15728 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(p, a, b) for (int p = a; p <= b; p++)
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << (sizeof...(b) ? ", " : " "); dbg(b...);}
void ent() {cout << "\n";}
/// ---- INITIAL END ----
const int INF = 1e15;
const int N = 200005;
pii a[N];
int l[N], r[N];
int from[N], dp[N];

int S[4 * N];
void update(int node, int l, int r, int id, int val) {
    if (l == r) {
        S[node] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (id <= mid)
        update(2 * node, l, mid, id, val);
    else
        update(2 * node + 1, mid + 1, r, id, val);
    S[node] = min(S[2 * node], S[2 * node + 1]);
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql <= l & r <= qr) {
        return S[node];
    }
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(2 * node, l, mid, ql, qr);
    else if (mid + 1 <= ql)
        return query(2 * node + 1, mid + 1, r, ql, qr);
    else
        return min(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr));
}

signed main() {
    IO;
    int n;
    cin >> n;
    FOR (i, 1, n) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    {
        /// build l[]
        deque<int> dq;
        for (int i = 1; i <= n; i++) {
            while (! dq.empty() && a[dq.back()].first - a[dq.back()].second >= a[i].first - a[i].second)
                dq.pop_back();
            if (dq.empty())
                l[i] = 1;
            else
                l[i] = dq.back() + 1;
            dq.push_back(i);
        }
    }
    {
        /// build r[]
        deque<int> dq;
        for (int i = n; i >= 1; i--) {
            while (! dq.empty() && a[dq.back()].first + a[dq.back()].second <= a[i].first + a[i].second)
                dq.pop_back();
            if (dq.empty())
                r[i] = n;
            else
                r[i] = dq.back() - 1;
            dq.push_back(i);
        }
    }
    // FOR (i, 1, n) dbg(l[i]); ent();
    // FOR (i, 1, n) dbg(r[i]); ent();
    fill(from, from + N, n + 1);
    FOR (i, 1, n) from[r[i]] = min(from[r[i]], l[i]);
    fill(dp, dp + N, INF);
    fill(S, S + 4 * N, INF);
    dp[0] = 0;
    update(1, 0, n, 0, 0);
    FOR (i, 1, n) {
        if (from[i] == n + 1) continue;
        dp[i] = query(1, 0, n, from[i] - 1, i - 1) + 1;
        update(1, 0, n, i, dp[i]);
    }
    cout << dp[n] << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:33:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   33 |     if (ql <= l & r <= qr) {
      |         ~~~^~~~

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