记录编号	601484	评测结果	AAAAAAAAAAAAAAAAAATT
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	90
用户昵称	健康铀	是否通过	未通过
代码语言	C++	运行时间	8.562 s
提交时间	2025-06-25 13:17:57	内存使用	7.16 MiB

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

const long long INF = -1e18;

struct F {
    vector<long long> t;
    int n;
    F(int s) {
        n = s;
        t.resize(n+1, INF);
    }
    void u(int p, long long v) {
        while (p <= n) {
            if (v > t[p]) 
                t[p] = v;
            p += p & -p;
        }
    }
    long long q(int p) {
        long long r = INF;
        while (p) {
            if (t[p] > r) 
                r = t[p];
            p -= p & -p;
        }
        return r;
    }
};

struct P {
    int t, p, v;
    long long A, B;
    P() {}
    P(int t, int p, int v, long long A, long long B) : t(t), p(p), v(v), A(A), B(B) {}
};

vector<P> a;
vector<long long> dp;
map<long long, int> m;

void cdq(int l, int r) {
    if (l >= r) 
        return;
    
    int m0 = (l + r) / 2;
    int t0 = a[m0].t;
    int rs = r+1;
    for (int i = m0+1; i <= r; i++) {
        if (a[i].t > t0) {
            rs = i;
            break;
        }
    }
    if (rs > r) {
        return;
    }
    
    cdq(l, rs-1);
    
    vector<int> le, ri;
    for (int i = l; i <= rs-1; i++) 
        le.push_back(i);
    for (int i = rs; i <= r; i++) 
        ri.push_back(i);
    
    sort(le.begin(), le.end(), [&](int i, int j) {
        if (a[i].A != a[j].A) 
            return a[i].A > a[j].A;
        else 
            return a[i].B < a[j].B;
    });
    
    sort(ri.begin(), ri.end(), [&](int i, int j) {
        if (a[i].A != a[j].A) 
            return a[i].A > a[j].A;
        else 
            return a[i].B < a[j].B;
    });
    
    int s = m.size();
    F f(s);
    
    int j = 0;
    for (int i = 0; i < ri.size(); i++) {
        int ir = ri[i];
        while (j < le.size() && a[le[j]].A >= a[ir].A) {
            int il = le[j];
            long long b = a[il].B;
            int p = m[b];
            f.u(p, dp[il]);
            j++;
        }
        long long b = a[ir].B;
        int p = m[b];
        long long tmp = f.q(p);
        if (tmp != INF) {
            if (tmp + a[ir].v > dp[ir]) {
                dp[ir] = tmp + a[ir].v;
            }
        }
    }
    
    cdq(rs, r);
}

int main() {
	freopen("free.in","r",stdin);
		freopen("free.out","w",stdout);
	 ios::sync_with_stdio(false);
	    cin.tie(nullptr);
    int w, n;
    cin>>w>>n;
    map<pair<int, int>, long long> mp;
    for (int i = 0; i < n; i++) {
        int t, p, v;
        cin>>t>>p>>v;
        mp[make_pair(t, p)] += v;
    }
    
    vector<P> a0;
    for (auto &it : mp) {
        int t = it.first.first;
        int p = it.first.second;
        long long v = it.second;
        long long A = (long long)p - 2ll * t;
        long long B = (long long)p + 2ll * t;
        a0.push_back(P(t, p, v, A, B));
    }
    n = a0.size();
    a = a0;
    
    sort(a.begin(), a.end(), [](const P &a, const P &b) {
        if (a.t != b.t) 
            return a.t < b.t;
        return a.p < b.p;
    });
    
    vector<long long> b;
    for (int i = 0; i < n; i++) {
        b.push_back(a[i].B);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    m.clear();
    for (int i = 0; i < b.size(); i++) {
        m[b[i]] = i+1;
    }
    
    dp.resize(n);
    for (int i = 0; i < n; i++) {
        dp[i] = a[i].v;
    }
    
    cdq(0, n-1);
    
    long long ans = *max_element(dp.begin(), dp.end());
    cout << ans << endl;
    
    return 0;
}