3350번: Candy Machine

https://www.acmicpc.net/problem/3350


$O(nlgn)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, r[100000], dp[100000], sz;
pair<int, int> p[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0, s, t; i < n; i++) {
        scanf("%d%d", &s, &t);
        p[i] = { t - s,s + t };
    }
    sort(p, p + n);
    for (int i = n; i--;) {
        int t = lower_bound(dp, dp + sz, p[i].second) - dp;
        dp[t] = p[i].second;
        r[i] = t;
        if (t == sz) sz++;
    }
    printf("%d", sz);
    for (int i = 0; i < n; i++) printf("\n%d %d %d", (p[i].second - p[i].first) / 2, (p[i].first + p[i].second) / 2, r[i] + 1);
    return 0;
}