yp155136 coding area

2017年4月18日星期二

(IOICamp_Judge) 導遊讚哥讚！ [重心剖分]

https://judge.ioicamp.org/problems/78

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

#define int long long

typedef long long LL;
const int MAX_N = 1e4 +6;
const int MAX_M = 1e4 +6;
const int MAX_P = 18;

struct Edge {
    int to;
    LL w;
    void _() {
        cout<<"to = "<<to<<" , w = "<<w<<endl;
    }
};

Edge MP(int _to,LL _w) {
    return Edge{_to,_w};
}

vector<Edge> edg[MAX_N];

struct Cen {
    int par;
    LL add;
    LL minus;
    int sz;
    void _() {
        cout<<"par = "<<par<<" , add = "<<add<<" , minus = "<<minus<<" , sz = "<<sz<<endl;
    }
} cen[MAX_N];

int now[MAX_N];
int depth[MAX_N];
Edge lca[MAX_P][MAX_N];
bool visit[MAX_N];
int stamp;
int tin[MAX_N],tout[MAX_N];

void dfs1(int id,int p,LL w,int cur_depth) {
    tin[id] = stamp++;
    visit[id] = 1;
    lca[0][id] = MP(p,w);
    depth[id] = cur_depth;
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs1(i.to,id,i.w,cur_depth+1);
        }
    }
    tout[id] = stamp++;
}

vector<int> v;
int sz[MAX_N];
int mx[MAX_N];

void dfs3(int id) {
    visit[id]=1;
    sz[id]=1;
    mx[id]=0;
    v.push_back(id);
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs3(i.to);
            sz[id] += sz[i.to];
            mx[id] = max(mx[id],sz[i.to]);
        }
    }
}

Cen MP4(int par,LL add,LL minus,int sz) {
    return Cen{par,add,minus,sz};
}

void dfs2(int id,int par_cen) {
    v.clear();
    dfs3(id);
    int can=-1;
    int tot=v.size();
    for (auto i:v) {
        visit[i]=0;
        if (max(mx[i],tot-sz[i]) <= tot/2) {
            can = i;
        }
    }
    visit[can]=true;
    cen[can] = MP4(par_cen,0,0,0);
    for (auto i:edg[can]) {
        if (!visit[i.to]) {
            dfs2(i.to,can);
        }
    }
}

bool is_anc(int son,int parent) {
    return tin[son] >= tin[parent] && tout[son] <= tout[parent];
}

LL get_dis(int x,int y) {
    if (depth[x] > depth[y]) swap(x,y);
    if (x==y) return 0;
    //x is lower
    if(is_anc(y,x)) {
        //we need only from y to x
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
    else {
        int tx=x,ty=y;
        x=tx,y=ty;
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        x=ty,y=tx;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
}

void add(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add += get_dis(now,id);
        cen[now].sz++;
        if (cen[now].par == -1) break;
        cen[now].minus += get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

void deleted(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add -= get_dis(now,id);
        cen[now].sz--;
        if (cen[now].par == -1) break;
        cen[now].minus -= get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

LL query(int id) {
    int now=id;
    LL ret=0;
    int totsz=0;
    while (now != -1) {
        ret += (cen[now].add - cen[now].minus);
        ret += (cen[now].sz - totsz)*get_dis(id,now);
        totsz = cen[now].sz;
        now = cen[now].par;
    }
    return ret;
}

main () {
    int T;
    scanf("%lld",&T);
    while (T--) {
        int n,m,q;
        scanf("%lld %lld %lld",&n,&m,&q);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>i;i++) {
            int a,b,c;
            scanf("%lld %lld %lld",&a,&b,&c);
            edg[a].push_back(MP(b,c));
            edg[b].push_back(MP(a,c));
        }
        stamp=0;
        memset(visit,0,sizeof(visit));
        dfs1(1,1,0,1);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                lca[i][j] = MP(lca[i-1][lca[i-1][j].to].to,lca[i-1][j].w+lca[i-1][lca[i-1][j].to].w);
            }
        }
        memset(visit,0,sizeof(visit));
        dfs2(1,-1);
        now[1]=1;
        for (int i=2;m>=i;i++) {
            add(1);
            now[i]=1;
        }
        while (q--) {
            int a,b;
            scanf("%lld %lld",&a,&b);
            if (a==1) {
                now[a]=b;
            }
            else {
                deleted(now[a]);
                now[a]=b;
                add(now[a]);
            }
            LL ret=query(now[1]);
            printf("%lld\n",ret);
            assert(ret>=0);
        }
    }
}

(TIOJ) 1903 . 【Gate】這個笑容由我來守護 - EXTREME [可刪邊並查集] [時間線段樹] [unodered_map]

http://tioj.ck.tp.edu.tw/problems/1903

((解釋有空再補))

#include <iostream>
#include <stdio.h>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <cassert>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
const LL MAX_N = 5e5 + 6;
namespace std {
  template <> struct hash<pii> {
    LL operator()(const pii &p) const {
      return p.first*MAX_N+p.second;
    }
  };
}

struct Node {
    static Node mem[4*MAX_N];
    Node *lc,*rc;
    vector<pii> v;
    Node() {
        lc=rc=NULL;
        v.clear();
    }
} Node::mem[4*MAX_N],*ptr=Node::mem;

Node* Build(int L,int R) {
    Node* node=new(ptr++)Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int l,int r,pii edge) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->v.push_back(edge);
        return;
    }
    int mid=(L+R)>>1;
    modify(node->lc,L,mid,l,r,edge);
    modify(node->rc,mid+1,R,l,r,edge);
}

int ans[MAX_N];

struct Event {
    int tx,ty;
    int ori_sz_tx,ori_sz_ty;
    int ori_p_tx,ori_p_ty;
    pii range;
    void gao(int _tx,int _ty,int _ori_sz_tx,int _ori_sz_ty,int _ori_p_tx,int _ori_p_ty,pii _range) {
        tx=_tx;
        ty=_ty;
        ori_sz_tx=_ori_sz_tx;
        ori_sz_ty=_ori_sz_ty;
        ori_p_tx=_ori_p_tx;
        ori_p_ty=_ori_p_ty;
        range=_range;
    }
};

vector<Event> ee;

struct DisjointSet {
    int p[MAX_N];
    int sz[MAX_N];
    int ans;
    void init(int n) {
        ans=n;
        for (int i=0;n>=i;i++) {
            p[i] = i;
            sz[i]=1;
        }
    }
    int Find(int x) {
        return p[x]==x?x:Find(p[x]);
    }
    void Union(int x,int y,pii range) {
        int tx=Find(x);
        int ty=Find(y);
        if (tx == ty) {
            return;
        }
        if (sz[tx] < sz[ty]) swap(tx,ty);
        assert(sz[tx]>=sz[ty]);
        Event e;
        e.gao(tx,ty,sz[tx],sz[ty],p[tx],p[ty],range);
        ee.push_back(e);
        sz[tx] += sz[ty];
        p[ty] = p[tx];
        ans--;
    }
    void recover(Event e) {
        p[e.tx] = e.ori_p_tx;
        p[e.ty] = e.ori_p_ty;
        sz[e.tx] = e.ori_sz_tx;
        sz[e.ty] = e.ori_sz_ty;
        ans++;
    }
} djs;

void visit(Node* node,int L,int R) {
    //deal with the edges
    pii range=make_pair(L,R);
    for (pii i:node->v) {
        djs.Union(i.first,i.second,range);
    }
    if (L==R) {
        ans[L] = djs.ans;
    }
    else {
        int mid=(L+R)>>1;
        visit(node->lc,L,mid);
        visit(node->rc,mid+1,R);
    }
    while (!ee.empty() && ee.back().range == range) {
        djs.recover(ee.back());
        ee.pop_back();
    }
}

LL hash(pii i) {
    return i.first*MAX_N+i.second;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        ptr=Node::mem;
        int n,m,q;
        scanf("%d %d %d",&n,&m,&q);
        djs.init(n);
        Node* root=Build(1,q+1);
        unordered_map<pii,pii> mp;  //start,count
        for (int i=1;m>=i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            pii ret=mp[edge];
            if (ret == make_pair(0,0)) ret=make_pair(1,1);
            else ret.second++;
            mp[edge]=ret;
        }
        int nn=q+1;
        for (int i=2;q+1>=i;i++) {
            getchar();
            char c;
            int a,b;
            scanf("%c %d %d",&c,&a,&b);
            if (a>b) swap(a,b);
            pii edge=make_pair(a,b);
            if (c=='N') {
                pii ret=mp[edge];
                if (ret == make_pair(0,0)) mp[edge] = make_pair(i,1);
                else {
                    ret.second++;
                    mp[edge]=ret;
                }
            }
            else if (c=='D') {
                pii ret=mp[edge];
                ret.second--;
                if (ret.second==0) {
                    modify(root,1,nn,ret.first,i-1,edge);
                    ret=make_pair(0,0);
                }
                mp[edge]=ret;
            }
        }
        for (auto p:mp) {
            pii edge=p.first;
            pii st=p.second;
            if (st.second==0) continue;
            modify(root,1,nn,st.first,q+1,edge);
        }
        visit(root,1,nn);
        for (int i=2;nn>=i;i++) {
            printf("%d\n",ans[i]);
        }
    }
}

(Zerojudge) b412: 【記憶中】之記憶中的并查集 [可持久化並查集]

https://zerojudge.tw/ShowProblem?problemid=b412

使用黑魔法rope XD

其實可用可持久化線段樹

有啟發式合併 + 路徑壓縮XD

#include <iostream>
#include <stdio.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

const int MAX_N = 1e5 + 6;

rope<int> *p[MAX_N],*sz[MAX_N];
int pp[MAX_N],szz[MAX_N];

int Find(int ver,int x) {
    int ret;
    if (p[ver]->at(x) == x) return x;
    ret = Find(ver,p[ver]->at(x));
    if (p[ver]->at(x) == ret) return ret;
    p[ver]->replace(x,ret);
    return ret;
}

void Union(int ver,int x,int y) {
    x = Find(ver,x);
    y = Find(ver,y);
    if (x==y) return;
    if (sz[ver]->at(x) > sz[ver]->at(y)) {
        sz[ver]->replace(x,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(y,x);
    }
    else {
        sz[ver]->replace(y,(sz[ver]->at(x) + sz[ver]->at(y)));
        p[ver]->replace(x,y);
    }
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    int ans=0;
    for (int i=0;n>=i;i++) {
        pp[i] = i;
        szz[i] = 1;
    }
    n+=3;
    p[0] = new rope<int>(pp,pp+n+1);
    sz[0]= new rope<int>(szz,szz+n+1);
    for (int i=1;m>=i;i++) {
        int a;
        scanf("%d",&a);
        a^=ans;
        if (a==0) {  //go to history version
            int b;
            scanf("%d",&b);
            b^=ans;
            p[i] = p[b];
            sz[i]=sz[b];
        }
        else if (a==1) {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            Union(i,b,c);
        }
        else {
            int b,c;
            scanf("%d %d",&b,&c);
            p[i] = new rope<int>(*p[i-1]);
            sz[i]= new rope<int>(*sz[i-1]);
            b^=ans;
            c^=ans;
            ans = (Find(i,b) == Find(i,c));
            printf("%d\n",ans);
        }
    }
}

(Zerojudge) d539: 區間 MAX [終極sparse-table]

https://zerojudge.tw/ShowProblem?problemid=d539

花O(n lg lg n)預處理，花O(1)查詢任意區間的RMQ。

想法：

把lgN東西分成一塊，對每一塊做Sparse-Table，
總複雜度為O( N/(lgN) * lgN * lg(lgN) ) = O(N lg lg N)

再對每一塊的Max做Sparse-Table : O( (N/lgN) * lg(N/lg(N)) ) = O(N)

之後就可以O(1)查詢。想想看吧！

//use sparse table + magic to <O(n lg lg n),O(1)>
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

const int MAX_N = 5e5 +60;
const int MAX_P = 22;
const int MAX_NN = 19;  //lg N
const int MAX_MM = 5;
const int MAX_NNN = 30000+6;
const int MAX_MMM = 16; //lg NN
const int _INF = -2147483648;

int a[MAX_N];
int st_small[MAX_NNN][MAX_MM][MAX_NN];
int st_big[MAX_MMM][MAX_NNN];
int lg2[MAX_N];
int pow2[MAX_P];

void make_st_small(int n,int *a,int st[MAX_MM][MAX_NN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_small(int st[MAX_MM][MAX_NN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void make_st_big(int n,int *a,int st[MAX_MMM][MAX_NNN]) {
    for (int i=0;n>i;i++) {
        st[0][i] = a[i];
    }
    for (int i=1;MAX_MMM>i;i++) {
        for (int j=0;n>j;j++) {
            int r=j+pow2[i-1];
            if (r>=n) r=n-1;
            st[i][j] = max(st[i-1][j],st[i-1][r]);
        }
    }
}

int query_big(int st[MAX_MMM][MAX_NNN],int l,int r) {
    int dis=(r-l+1);
    return max(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]);
}

void init() {
    pow2[0]=1;
    for (int i=1;MAX_P>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    lg2[1] = 0;
    int id=1;
    for (int i=2;MAX_N>i;i++) {
        if (i==pow2[id]) {
            lg2[i] = lg2[i-1]+1;
            id++;
        }
        else {
            lg2[i] = lg2[i-1];
        }
    }
}

int tmp[MAX_NN];
int aa[MAX_NNN];

int main () {
    init();
    int n;
    scanf("%d",&n);
    for (int i=0;n>i;i++) {
        scanf("%d",&a[i]);
    }
    int small_sz=lg2[n];
    if (small_sz<2) small_sz=2;
    int totgroup=n/small_sz + !(n%small_sz==0);
    for (int i=0;totgroup>i;i++) {
        int t=0;
        for (int j=i*small_sz;i*small_sz+small_sz>j;j++) {
            if (j<n) tmp[t++] = a[j];
            else tmp[t++] = _INF;
        }
        make_st_small(small_sz,tmp,st_small[i]);
        aa[i] = query_small(st_small[i],0,small_sz-1);
    }
    make_st_big(totgroup,aa,st_big);
    int q;
    scanf("%d",&q);
    while (q--) {
        int l,r;
        scanf("%d %d",&l,&r);
        if (l>r) swap(l,r);
        l--;
        r--;
        if (l/small_sz == r/small_sz) {
            //in the same group
            int group_first=(l/small_sz)*small_sz;
            printf("%d\n",query_small(st_small[l/small_sz],l-group_first,r-group_first));
            continue;
        }
        int ans=max(query_small(st_small[l/small_sz],l-(l/small_sz)*small_sz,small_sz-1),
        query_small(st_small[r/small_sz],0,r-(r/small_sz)*small_sz));
        if (l/small_sz +1 == r/small_sz) printf("%d\n",ans);
        else printf("%d\n",max(ans,query_big(st_big,l/small_sz+1,r/small_sz-1)));
    }
}

(Zerojudge) d779: NOIP2009 3.最优贸易

https://zerojudge.tw/ShowProblem?problemid=d779

我是先想50%，之後才想到100%的！

在寫50%的時候，我發現圖是一個DAG，用DAG來維護一些東西。

那在推廣到100%的時候，我就在想，要怎麼把整張圖推廣到DAG --> SCC！

50%的版本：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 1e5 +6;

vector<int> edg[MAX_N];
int a[MAX_N];
int mn[MAX_N];
int mxans[MAX_N];
int deg[MAX_N];

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
        mn[i] = a[i];
        mxans[i]=0;
    }
    for (int i=0;m>i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if (c==1) edg[a].push_back(b);
        else {
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        deg[b]++;
    }
    int ans=0;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        mxans[t] = max(mxans[t],a[t]-mn[t]);
        for (int i:edg[t]) {
            mn[i] = min(mn[i],mn[t]);
            deg[i]--;
            mxans[i] = max(mxans[i],mxans[t]);
            if (deg[i]==0) que.push(i);
        }
    }
    printf("%d\n",mxans[n]);
}

100%的版本：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = 1e5 + 6;
const int INF = 1e9 + 7;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
vector<int> scc_edg[MAX_N];
int scc_mx[MAX_N],scc_mn[MAX_N],scc_ans[MAX_N];
int a[MAX_N];
bool visit[MAX_N];
int get_stamp[MAX_N];
int in_scc[MAX_N];
int ansmx[MAX_N];
int deg[MAX_N];

void gao1(int id,int &stamp) {
    visit[id]=1;
    for (int i:rev_edg[id]) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    get_stamp[stamp++]=id;
}

void gao2(int id,int scc) {
    visit[id]=1;
    for (int i:edg[id]) {
        if (!visit[i]) {
            gao2(i,scc);
        }
    }
    in_scc[id]=scc;
    scc_mx[scc] = max(scc_mx[scc],a[id]);
    scc_mn[scc] = min(scc_mn[scc],a[id]);
}

int build_scc(int n) {
    memset(visit,0,sizeof(visit));
    int stamp=1;
    for (int i=1;n>=i;i++) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    fill(scc_mx,scc_mx+MAX_N,-INF);
    fill(scc_mn,scc_mn+MAX_N,INF);
    memset(visit,0,sizeof(visit));
    int scc=0;
    for (int i=n;i>=1;i--) {
        if (!visit[get_stamp[i]]) {
            gao2(get_stamp[i],++scc);
        }
    }
    for (int i=1;n>=i;i++) {
        for (int j:edg[i]) {
            if (in_scc[i] != in_scc[j]) {
//                cout<<"build edge i = "<<in_scc[i]<<" , j = "<<in_scc[j]<<endl;
                scc_edg[in_scc[i]].push_back(in_scc[j]);
            }
        }
    }
    return scc;
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
    }
    for (int i=1;m>=i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        edg[a].push_back(b);
        rev_edg[b].push_back(a);
        if (c==2) {
            edg[b].push_back(a);
            rev_edg[a].push_back(b);
        }
    }
    int scc=build_scc(n);
//    cout<<"scc = "<<scc<<endl;
//    for (int i=1;n>=i;i++) {
//        cout<<"in_scc["<<i<<"] = "<<in_scc[i]<<endl;
//    }
    queue<int> que;
    for (int i=1;scc>=i;i++) {
        for (int j:scc_edg[i]) {
            deg[j]++;
        }
    }
    que.push(in_scc[1]);
    while (!que.empty()) {
        int t=que.front();
//        cout<<"T = "<<t<<endl;
        que.pop();
        ansmx[t] = max(ansmx[t],scc_mx[t]-scc_mn[t]);
        for (int i:scc_edg[t]) {
            deg[i]--;
            scc_mn[i] = min(scc_mn[i],scc_mn[t]);
            ansmx[i] = max(ansmx[i],ansmx[t]);
            if (deg[i] == 0) que.push(i);
        }
    }
    printf("%d\n",ansmx[in_scc[n]]);
}

2017年4月12日星期三

(SPOJ) RPLN - Negative Score [Sparse-Table]

http://www.spoj.com/problems/RPLN/

implement with sparse table

<O(n lg n), O(1)>

//use sparse table
#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e5 +6;
const int MAX_P = 18;

int a[MAX_N];
int st[MAX_P][MAX_N];
int lg2[MAX_N];
int pow2[MAX_P];

int main () {
    pow2[0]=1;
    for (int i=1;MAX_P>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    lg2[1] = 0;
    int id=1;
    for (int i=2;MAX_N>i;i++) {
        if (i==pow2[id]) {
            lg2[i] = lg2[i-1]+1;
            id++;
        }
        else {
            lg2[i] = lg2[i-1];
        }
    }
    int T;
    scanf("%d",&T);
    int cases=0;
    while (T--) {
        int n,q;
        scanf("%d %d",&n,&q);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            st[0][i] = a[i];
        }
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                int r=j+pow2[i-1];
                if (r>n) r=n;
                st[i][j] = min(st[i-1][j],st[i-1][r]);
            }
        }
        printf("Scenario #%d:\n",++cases);
        while (q--) {
            int l,r;
            scanf("%d %d",&l,&r);
            int dis=(r-l+1);
            printf("%d\n",min(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]));
        }
    }
}

2017年4月7日星期五

(UVA) 1106 - Machine Works [CDQ分治] [DP斜率優化]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3547

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] - 1)*g[j])

typedef long long LL;
typedef __int128 LLL;
const int MAX_N = 1e5 + 6;

struct Mac {
    LL t,p,r,g;
    void input() {
        scanf("%lld %lld %lld %lld",&t,&p,&r,&g);
    }
} mac[MAX_N];

struct Line {
    LLL m,b;
    Line(LL _m,LL _b) {
        m=_m;
        b=_b;
    }
    LLL val(LLL x) {
        return m*x+b;
    }
};

bool operator<(const Mac &m1,const Mac &m2) {
    return m1.t < m2.t;
}

bool operator<(const Line &l1,const Line &l2) {
    return l1.m < l2.m || l1.m==l2.m && l1.b<l2.b;
}

LL dp[MAX_N];

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] + 1)*g[j])

bool check(Line _0,Line _1,Line _2) {
    return (_0.m-_2.m)*(_0.b-_1.b) > (_0.b-_2.b)*(_0.m-_1.m);
}

void do_things(int L,int R) {
    int mid=(L+R)>>1;
    vector<Line> v;
    for (int j=L;mid>=j;j++) {
        if (dp[j] >= mac[j].p) {
            v.push_back(Line(mac[j].g,dp[j]+mac[j].r-mac[j].p+(-mac[j].t-1)*mac[j].g));
        }
    }
    sort(v.begin(),v.end());
    vector<Line> dq;   //use vector as deque XD
    for (Line l:v) {
        while (dq.size()   && dq[dq.size()-1].m == l.m) dq.pop_back();
        while (dq.size()>1 && check(l,dq[dq.size()-1],dq[dq.size()-2])) dq.pop_back();
        dq.push_back(l);
    }
    if (!dq.size()) return;
    int now=0;
    for (int i=mid+1;R>=i;i++) {
        while (now+1<dq.size() && dq[now].val(mac[i].t) < dq[now+1].val(mac[i].t)) now++;
        dp[i] = max(LLL(dp[i]),dq[now].val(mac[i].t));
    }
}

void cdq(int L,int R) {
    if (L==R) return;
    int mid=(L+R)>>1;
    cdq(L,mid);
    do_things(L,R);
    cdq(mid+1,R);
}

int main () {
    int n,c,d;
    int cases=0;
    while (scanf("%d %d %d",&n,&c,&d) != EOF) {
        if (!n && !c && !d) break;
        printf("Case %d: ",++cases);
        for (int i=1;n>=i;i++) {
            mac[i].input();
        }
        memset(dp,0,sizeof(dp));
        mac[0]=Mac{0,0,c,0};
        mac[n+1]=Mac{d+1,0,0,0};
        sort(mac,mac+(n+2));
        cdq(0,n+1);
        printf("%lld\n",dp[n+1]);
    }
}

訂閱：文章 (Atom)

2017年4月18日 星期二

2017年4月12日 星期三

2017年4月7日 星期五

2017年4月18日星期二

2017年4月12日星期三

2017年4月7日星期五