Tác giả: skyvn97

Xem: https://www.youtube.com/live/qWz664WCmJw?si=mX9ZCtS6Ry5dFNqq

// Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 400005;
const int INF = 1000000000;

struct Sign {
    int x, a, b;
    Sign(int x = 0, int a = 0, int b = 0) : x(x), a(a), b(b) {}
};

struct SegmentTree {
   private:
    int treeSize;
    vector<int> nodes, leaf;
    int current_value;
    int merge(int a, int b) {
        if (a == -INF) {
            return b;
        }
        if (a == INF) {
            return INF;
        }
        if (b == -INF) {
            return a;
        }
        if (b == INF) {
            return INF;
        }
        if (a == b) {
            return a;
        }
        return INF;
    }
    void initTree(int id, int low, int high, int initial_value[]) {
        if (low == high) {
            nodes[id] = initial_value[low];
            leaf[low] = id;
            return;
        }
        int mid = (low + high) / 2;
        initTree(id * 2, low, mid, initial_value);
        initTree(id * 2 + 1, mid + 1, high, initial_value);
        nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]);
    }
    int get(int id, int low, int high, int pos) {
        if (high < pos) {
            return high + 1;
        }
        if (low >= pos) {
            if (nodes[id] == -INF) {
                return high + 1;
            }
            if (current_value == -INF) {
                if (nodes[id] == -INF) {
                    return high + 1;
                }
                if (nodes[id] != INF) {
                    current_value = nodes[id];
                    return high + 1;
                }
            }
            if (nodes[id] == current_value) {
                return high + 1;
            }
        }
        if (low == high) {
            return low;
        }
        int mid = (low + high) / 2;
        int result = get(id * 2, low, mid, pos);
        if (result == mid + 1) {
            result = get(id * 2 + 1, mid + 1, high, pos);
        }
        return result;
    }

   public:
    void init(int treeSize, int initial_value[]) {
        this->treeSize = treeSize;
        int tmp = 1;
        while (tmp < treeSize) {
            tmp *= 2;
        }
        nodes.resize(tmp * 2);
        leaf.resize(treeSize + 1);
        initTree(1, 1, treeSize, initial_value);
    }
    void update(int pos, int val) {
        int id = leaf[pos];
        nodes[id] = val;
        while (id > 1) {
            id /= 2;
            nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]);
        }
    }
    int get(int pos) {
        current_value = -INF;
        return get(1, 1, treeSize, pos) - pos;
    }
} smt;

int n;
Sign signs[MAX_N];
int nextLeft[MAX_N], nextRight[MAX_N];
pair<int, int> positions[MAX_N];
int base_value[MAX_N];

void initNextArray() {
    nextLeft[n] = n + 1;
    nextRight[n] = n + 1;
    for (int i = n - 1; i >= 1; i--) {
        nextLeft[i] = nextLeft[i + 1];
        nextRight[i] = nextRight[i + 1];
        if (signs[i].x - signs[i].a != signs[i + 1].x - signs[i + 1].a) {
            nextLeft[i] = i + 1;
        }
        if (signs[i].x + signs[i].b != signs[i + 1].x + signs[i + 1].b) {
            nextRight[i] = i + 1;
        }
    }
}

pair<int, int> solve() {
    sort(positions + 1, positions + n + 1);
    smt.init(n, base_value);
    int left = 1;
    int maxLength = 0, numChoices = 0;
    while (left <= n) {
        int right = left;
        while (right < n &&
               positions[right + 1].first == positions[left].first) {
            right++;
        }
        for (int i = left; i <= right; i++) {
            int pos = positions[i].second;
            smt.update(pos, -INF);
        }
        for (int i = left; i <= right; i++) {
            int tmp = smt.get(positions[i].second);
            if (tmp > maxLength) {
                maxLength = tmp;
                numChoices = 1;
            } else if (tmp == maxLength) {
                numChoices++;
            }
        }
        for (int i = left; i <= right; i++) {
            int pos = positions[i].second;
            smt.update(pos, base_value[pos]);
        }
        left = right + 1;
    }
    return make_pair(maxLength, numChoices);
}

int main() {
#ifdef ONLINE_JUDGE
    freopen("roadsigns.inp", "r", stdin);
    freopen("roadsigns.out", "w", stdout);
#endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> signs[i].x >> signs[i].a >> signs[i].b;
    }
    initNextArray();
    if (nextLeft[1] == n + 1 || nextRight[1] == n + 1) {
        cout << n << " " << -1 << "\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        positions[i] = make_pair(signs[i].x - signs[i].a, i);
        base_value[i] = signs[i].x + signs[i].b;
    }
    pair<int, int> result = solve();
    for (int i = 1; i <= n; i++) {
        positions[i] = make_pair(signs[i].x + signs[i].b, i);
        base_value[i] = signs[i].x - signs[i].a;
    }
    pair<int, int> tmp = solve();
    if (tmp.first > result.first) {
        result = tmp;
    } else if (tmp.first == result.first) {
        result.second += tmp.second;
    }
    cout << result.first << ' ' << result.second << '\n';
    return 0;
}