某島

… : "…アッカリ~ン . .. . " .. .
March 18, 2020

BZOJ 3218. a + b Problem

const int N = int(1e5) + 9;
int a[N], l[N], r[N]; VI I;
int n, z;

struct Dinitz {
    const static int M = N*20;
    int D[N], hd[N], suc[M], to[M], cap[M];
    int n, m, s, t;
    inline void ae(int x, int y, int c){
        suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
        suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0;
    }
#define v to[i]
#define c cap[i]
#define f cap[i^1]
    bool bfs(){
        static int Q[N]; int cz = 0, op = 1;
        fill(D, D+n, 0); D[Q[0] = s] = 1; while (cz < op){
            int u = Q[cz++]; REP_G(i, u) if (!D[v]&&c){
                D[Q[op++]=v] = D[u]+1;
                if (v==t) return 1;
            }
        }
        return 0;
    }

    LL run(){
        LL z=0; while (bfs()){
            static int cur[N], pre[N];
            int u=s;pre[s]=-1;cur[s]=hd[s];while (~u){
#define i cur[u]
                if (u==t){
                    int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);
                    z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;
                }
#undef i
                int i;for(i=cur[u];i;i=suc[i])if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;}
                if (!i)D[u]=0,u=pre[u];
            }
        }
        return z;
    }
#undef f
#undef c
#undef v
    void init() {
        RD(n); m=2,s=2*n+1,t=2*n+2;
        REP_1(i, n) {
            I.PB(RD(a[i])); int b, w; RD(b, w); z += b+w;
            I.PB(RD(l[i])); I.PB(RD(r[i]));
            ae(s,i,b); ae(i,t,w); ae(i,n+i,RD());
        }
        UNQ(I); REP_1(i, n) {
            a[i]=LBD(I,a[i])+1;
            l[i]=LBD(I,l[i])+1;
            r[i]=LBD(I,r[i])+1;
        }
        ::n = n; n = t+1;
    }
} G;

struct Presitent_Segment_Tree {
    const static int N = ::N * 10;
#define lx l[x]
#define rx r[x]
#define ml (ll + rr >> 1)
#define mr (ml + 1)
    int l[N], r[N], nn;
    int n, s, t, a, b;

    void add_edge(int x, int y) {
        G.ae(G.t+x, G.t+y, INF);
    }

    inline int new_node(int y) {
        int x = ++nn; G.n += 1;
        if (y) {
            lx = l[y]; rx = r[y];
            add_edge(x, y);
        }
        return x;
    }
    int add(int y, int p, int t) {
        int x = new_node(y), root = x, ll = 1, rr = n;
        while (ll < rr) {
            if (p < mr) {
                add_edge(x, lx = new_node(lx));
                x = lx; rr = ml;
            } else {
                add_edge(x, rx = new_node(rx));
                x = rx; ll = mr;
            }
        }
        add_edge(x, t);
        return root;
    }
	void gao(int x,int ll,int rr) {
		if (!x || b < ll || rr < a) return;
		if (a <= ll && rr <= b) {
			add_edge(s, x);
			return;
		}
		gao(lx,ll,ml);
		gao(rx,mr,rr);
	}
	void gao(int x, int a, int b, int s) {
	    this->a = a; this->b = b; this->s = s;
	    gao(x, 1, n);
	}
} T; int root[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	G.init(); T.n = SZ(I); REP_1(i, n) {
		T.gao(root[i-1],l[i],r[i],n+i-G.t);
		root[i]=T.add(root[i-1],a[i],i-G.t);
	}

	printf("%d\n", z - G.run());
}