QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344444#4897. 音符大师ANIG0 8ms213868kbC++148.4kb2024-03-04 16:11:202024-03-04 16:11:21

Judging History

你现在查看的是最新测评结果

  • [2024-03-04 16:11:21]
  • 评测
  • 测评结果：0
  • 用时：8ms
  • 内存：213868kb
查看
  • [2024-03-04 16:11:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,inf=1e15;
namespace sgt{
    struct node{
        int l,r,sm;
    }p[N<<2];
    void upset(int x){
        p[x].sm=min(p[x<<1].sm,p[x<<1|1].sm);
    }
    void reset(int x,int l,int r){
        p[x].l=l,p[x].r=r;
        p[x].sm=inf;
        if(l==r)return;
        int mid=l+r>>1;
        reset(x<<1,l,mid);
        reset(x<<1|1,mid+1,r);
    }
    void sets(int x,int d,int sm){
        if(p[x].l==p[x].r){
            p[x].sm=sm;
            return;
        }
        int mid=p[x].l+p[x].r>>1;
        if(d<=mid)sets(x<<1,d,sm);
        else sets(x<<1|1,d,sm);
        upset(x);
    }
    int gets(int x,int l,int r){
        if(l>r)return inf;
        if(l<=p[x].l&&r>=p[x].r)return p[x].sm;
        int mid=p[x].l+p[x].r>>1;
        if(r<=mid)return gets(x<<1,l,r);
        if(l>mid)return gets(x<<1|1,l,r);
        return min(gets(x<<1,l,r),gets(x<<1|1,l,r));
    }
}
namespace tr{
    struct node{
        int sm1,sm2,laz;
        signed lson,rson;
    }p[N*100];
    int idx,w[N],f[5005][5005];
    int nw(){
        idx++;
        p[idx].sm1=p[idx].sm2=inf;
        return idx;
    }
    void init(int x){
        if(!p[x].lson)p[x].lson=nw();
        if(!p[x].rson)p[x].rson=nw();
    }
    void add(int x,int sm){
        p[x].sm1+=sm;
        p[x].sm2+=sm;
        p[x].laz+=sm;
    }
    void dnset(int x){
        if(p[x].laz){
            add(p[x].lson,p[x].laz);
            add(p[x].rson,p[x].laz);
            p[x].laz=0;
        }
    }
    void upset(int x){
        p[x].sm1=min(p[p[x].lson].sm1,p[p[x].rson].sm1);
        p[x].sm2=min(p[p[x].lson].sm2,p[p[x].rson].sm2);
    }
    void sets(int x,int d,int sm,int nl,int nr){
        if(nl==nr){
            p[x].sm1=min(p[x].sm1,sm-w[d]);
            p[x].sm2=min(p[x].sm2,sm+w[d]);
            return;
        }
        int mid=nl+nr>>1;
        init(x);
        dnset(x);
        if(d<=mid)sets(p[x].lson,d,sm,nl,mid);
        else sets(p[x].rson,d,sm,mid+1,nr);
        upset(x);
    }
    int gets1(int x,int l,int r,int nl,int nr){
        if(!x)return inf;
        if(l<=nl&&r>=nr)return p[x].sm1;
        int mid=nl+nr>>1;
        dnset(x);
        if(r<=mid)return gets1(p[x].lson,l,r,nl,mid);
        if(l>mid)return gets1(p[x].rson,l,r,mid+1,nr);
        return min(gets1(p[x].lson,l,r,nl,mid),gets1(p[x].rson,l,r,mid+1,nr));
    }
    int gets2(int x,int l,int r,int nl,int nr){
        if(!x)return inf;
        if(l<=nl&&r>=nr)return p[x].sm2;
        int mid=nl+nr>>1;
        dnset(x);
        if(r<=mid)return gets2(p[x].lson,l,r,nl,mid);
        if(l>mid)return gets2(p[x].rson,l,r,mid+1,nr);
        return min(gets2(p[x].lson,l,r,nl,mid),gets2(p[x].rson,l,r,mid+1,nr));
    }
    int gets(int x,int d,int nl,int nr){
        if(!x)return inf;
        if(nl==nr)return p[x].sm1+w[nl];
        int mid=nl+nr>>1;
        dnset(x);
        if(d<=mid)return gets(p[x].lson,d,nl,mid);
        else return gets(p[x].rson,d,mid+1,nr);
    }
    void hb(int a,int b,int nl,int nr){
        if(nl==nr){
            p[a].sm1=min(p[a].sm1,p[b].sm1);
            p[a].sm2=min(p[a].sm2,p[b].sm2);
            return;
        }
        int mid=nl+nr>>1;
        dnset(a);dnset(b);
        if(p[a].lson){
            if(p[b].lson)hb(p[a].lson,p[b].lson,nl,mid);
        }else if(p[b].lson)p[a].lson=p[b].lson;
        if(p[a].rson){
            if(p[b].rson)hb(p[a].rson,p[b].rson,mid+1,nr);
        }else if(p[b].rson)p[a].rson=p[b].rson;
        upset(a);
    }
}
int n,k,p[N],nxt1[N],nxt2[N],al,res=inf,rt[N];
vector<int>ls;
int gets(int x){
    return upper_bound(ls.begin(),ls.end(),x)-ls.begin();
}
void chk(int&a,int b){
    a=min(a,b);
}
struct node{
    int l1,r1,l2,r2;
    friend bool operator<(node a,node b){
        if(a.l1!=b.l1)return a.l1<b.l1;
        if(a.r1!=b.r1)return a.r1<b.r1;
        if(a.l2!=b.l2)return a.l2<b.l2;
        return a.r2<b.r2;
    }
};
map<node,int>mp[N];
int gets(int nw,int l1,int r1,int l2,int r2){
    return mp[nw][{l1,r1,l2,r2}];
}
vector<node>q[N];
signed main(){
    memset(tr::f,0x3f,sizeof(tr::f));
    freopen("ex_game2.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        ls.push_back(p[i]);
        if(p[i]-k>=0)ls.push_back(p[i]-k);
    }
    ls.push_back(0);
    sort(ls.begin(),ls.end());
    ls.resize(unique(ls.begin(),ls.end())-ls.begin());
    al=ls.size();
    for(int i=1;i<=al;i++)tr::w[i]=ls[i-1];
    tr::p[0].sm1=tr::p[0].sm2=inf;
    sgt::reset(1,1,al);
    for(int i=n;i>=0;i--){
        int a=gets(p[i]-k),b=gets(p[i]),c=gets(p[i]+k);
        nxt1[i]=min(sgt::gets(1,1,a-1),sgt::gets(1,b+1,al));
        nxt2[i]=min(sgt::gets(1,1,b-1),sgt::gets(1,c+1,al));
        sgt::sets(1,b,i);
    }
    for(int i=0;i<=n;i++){
        int a,b,c,d;
        if(nxt1[i]<=n){
            a=gets(p[nxt1[i]]-k),b=gets(p[nxt1[i]]);
            for(int j=b;j>=a;j--)q[i].push_back({p[i]-k,p[i],ls[j-1],ls[j-1]+k});
        }
        if(nxt2[i]<=n){
            a=gets(p[nxt2[i]]-k),b=gets(p[nxt2[i]]);
            for(int j=b;j>=a;j--)q[i].push_back({p[i],p[i]+k,ls[j-1],ls[j-1]+k});
        }
    }
    sgt::reset(1,1,al);
    for(int i=n;i>=0;i--){
        for(int j=0;j<q[i].size();j++){
            int l1=gets(q[i][j].l1),r1=gets(q[i][j].r1),l2=gets(q[i][j].l2),r2=gets(q[i][j].r2);
            if(l1>l2)swap(l1,l2),swap(r1,r2);
            mp[i][q[i][j]]=min({sgt::gets(1,1,l1-1),sgt::gets(1,r1+1,l2-1),sgt::gets(1,r2+1,al)});
        }
        sgt::sets(1,gets(p[i]),i);
    }
    for(int i=0;i<=n;i++)rt[2*i]=tr::nw(),rt[2*i+1]=tr::nw();
    tr::sets(rt[1],1,0,1,al);
    for(int i=0;i<=n;i++){
        int a,b,c,d;
        if(nxt1[i]>n){
            for(int j=1;j<=al;j++)res=min(res,tr::gets(rt[2*i],j,1,al));
        }else{
            a=gets(p[nxt1[i]]-k),b=gets(p[nxt1[i]]),c=gets(p[i]-k),d=gets(p[i]);
            for(int j=b;j>=a;j--){
                int to=gets(i,p[i]-k,p[i],ls[j-1],ls[j-1]+k);
                if(to>n){
                    res=min(res,tr::gets(rt[2*i],j,1,al));
                    continue;
                }
                if(p[to]>p[i])tr::sets(rt[2*to],j,tr::gets(rt[2*i],j,1,al)+p[to]-p[i],1,al);
                else tr::sets(rt[2*to+1],j,tr::gets(rt[2*i],j,1,al)+p[i]-p[to]-k,1,al);
                if(ls[j-1]<p[to])tr::sets(rt[2*to],c,tr::gets(rt[2*i],j,1,al)+p[to]-ls[j-1]-k,1,al);
                else tr::sets(rt[2*to+1],c,tr::gets(rt[2*i],j,1,al)+ls[j-1]-p[to],1,al);
            }
            if(p[nxt1[i]]>p[i])for(int j=1;j<=al;j++)tr::sets(rt[2*nxt1[i]],j,tr::gets(rt[2*i],j,1,al)+p[nxt1[i]]-p[i],1,al);
            else for(int j=1;j<=al;j++)tr::sets(rt[2*nxt1[i]+1],j,tr::gets(rt[2*i],j,1,al)+p[i]-p[nxt1[i]]-k,1,al);
            for(int j=1;j<a;j++)tr::sets(rt[2*nxt1[i]],c,tr::gets(rt[2*i],j,1,al)+p[nxt1[i]]-ls[j-1]-k,1,al);
            for(int j=b+1;j<=al;j++)tr::sets(rt[2*nxt1[i]+1],c,tr::gets(rt[2*i],j,1,al)+ls[j-1]-p[nxt1[i]],1,al);
        }
        if(nxt2[i]>n){
            for(int j=1;j<=al;j++)res=min(res,tr::gets(rt[2*i+1],j,1,al));
        }else{
            a=gets(p[nxt2[i]]-k),b=gets(p[nxt2[i]]),c=gets(p[i]),d=gets(p[i]+k);
            for(int j=b;j>=a;j--){
                int to=gets(i,p[i],p[i]+k,ls[j-1],ls[j-1]+k);
                if(to>n){
                    res=min(res,tr::gets(rt[2*i+1],j,1,al));
                    continue;
                }
                if(p[to]>p[i])tr::sets(rt[2*to],j,tr::gets(rt[2*i+1],j,1,al)+p[to]-p[i]-k,1,al);
                else tr::sets(rt[2*to+1],j,tr::gets(rt[2*i+1],j,1,al)+p[i]-p[to],1,al);
                if(ls[j-1]<p[to])tr::sets(rt[2*to],c,tr::gets(rt[2*i+1],j,1,al)+p[to]-ls[j-1]-k,1,al);
                else tr::sets(rt[2*to+1],c,tr::gets(rt[2*i+1],j,1,al)+ls[j-1]-p[to],1,al);
            }
            if(p[nxt2[i]]>p[i])for(int j=1;j<=al;j++)tr::sets(rt[2*nxt2[i]],j,tr::gets(rt[2*i+1],j,1,al)+p[nxt2[i]]-p[i]-k,1,al);
            else for(int j=1;j<=al;j++)tr::sets(rt[2*nxt2[i]+1],j,tr::gets(rt[2*i+1],j,1,al)+p[i]-p[nxt2[i]],1,al);
            for(int j=1;j<a;j++)tr::sets(rt[2*nxt2[i]],c,tr::gets(rt[2*i+1],j,1,al)+p[nxt2[i]]-ls[j-1]-k,1,al);
            for(int j=b+1;j<=al;j++)tr::sets(rt[2*nxt2[i]+1],c,tr::gets(rt[2*i+1],j,1,al)+ls[j-1]-p[nxt2[i]],1,al);
        }
    }
    cout<<res;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 213324kb

input:

200 20
78 30 163 87 97 53 96 76 81 138 156 200 124 93 173 119 115 93 150 99 22 80 88 131 61 126 47 103 143 142 129 186 89 105 101 143 178 110 13 77 79 178 21 108 200 146 87 105 54 61 136 69 161 195 13 105 18 151 25 191 30 35 90 110 17 98 181 58 120 102 139 71 59 24 72 84 33 12 28 82 23 80 128 96 115...

output:

0

result:

wrong answer 1st lines differ - expected: '3669', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 8ms
memory: 213868kb

input:

50000 0
957304147 455870042 888520405 388924006 685268286 213595280 898496267 50362797 310595209 105517171 706682592 663787741 927429771 306122736 1352192 453945549 31881610 943782347 779421515 543589796 209926777 908434673 845417119 374441290 190474943 606994057 30091060 491598457 644246786 4649716...

output:

0

result:

wrong answer 1st lines differ - expected: '7861788079227', found: '0'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%
English 繁體中文 简体中文

Server Time: 2024-11-30 10:33:12 | OpenSource Project