ch_POJ1201 Intervals

描述可也太毒瘤了

#include<iostream>
#include<cstdio>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#include<cstring>

#define I inline
#define NN 50005
#define MM 500005

namespace xds_dj {
#define XX 1000005
    u d[NN],used[NN],vt[NN],h[NN],q[XX],cnt;
    struct node {
        u to,next,va;
    } a[MM<<1];
    inline void add(const u &x,const u &y,const u &z) {
        //printf("%d -> %d = %d
",x,y,z);
        a[++cnt].next=h[x],a[cnt].to=y,a[cnt].va=z,h[x]=cnt;
    }
    inline void pri() {
        std::memset(vt,0,sizeof(vt));
        std::memset(used,0,sizeof(used));
        std::memset(h,0,sizeof(h));
        cnt=0;
    }
    u run(const u &x,const u &n) {
        ri l(0),r(0),k;
        std::memset(d,-0x3f,sizeof(d)),d[x]=0,q[++r]=x,++used[x];
        while(l<r) {
            k=q[++l],vt[k]=0;
            for(ri i=h[k]; i; i=a[i].next) {
                u y=a[i].to,z=a[i].va;
                //printf("%d -> %d = %d
",k,y,z);
                if(d[k]+z>d[y]) {
                    d[y]=d[k]+z;
                    if(!vt[y]) {
                        vt[y]=1,q[++r]=y;
                        /*used[y]++;
                        if(used[y]>n) {
                            pri();//多次
                            return 0;//负环
                        }*/
                    }
                }
            }
        }
        //pri();//多次
        //return 1;//负环
    }
#undef XX


}

#include<algorithm>

namespace mainstay {

    u N,mx;

    using namespace xds_dj;

    inline void solve() {
        N=in();
        for(ri i(1); i<=N; ++i) {
            u _a(in()+1),_b(in()+1),_c(in());
            mx=std::max(mx,_b);
            add(_a-1,_b,_c);
        }
        for(ri i(1); i<=mx; ++i) add(i-1,i,0),add(i,i-1,-1);
        //printf("
");
        run(0,mx),printf("%d",d[mx]);
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}