Submission #331832

#	Time	Username	Problem	Language	Result	Execution time	Memory
331832		vipghn2003	Colouring a rectangle (eJOI19_colouring)	C++14	0 / 100	1101 ms	64364 KiB

colouring

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;

const int N=4e5+5;
int n,m,a[N],b[N],l[N],r[N],s[N];

struct data
{
    int a,l,r;
}val[N];

bool lf(data p,data q)
{
    return p.l<q.l;
}

struct SegmentTree
{
    ll ST[4*N];
    ll lazy[4*N];

    void dolazy(int id,int l,int r)
    {
        if (lazy[id]==0) return;
        ST[id]+=lazy[id];
        if (l!=r)
        {
            lazy[id*2]+=lazy[id];
            lazy[id*2+1]+=lazy[id];
        }
        lazy[id]=0;
    }

    void update_range(int id,int l,int r,int L,int R,ll val)
    {
        dolazy(id,l,r);
        if (r<L||R<l) return;
        if(L<=l&&r<=R)
        {
            ST[id]+=val;
            if (l!=r)
            {
                lazy[id*2]+=val;
                lazy[id*2+1]+=val;
            }
            return;
        }
        int mid=(l+r)/2;
        update_range(id*2,l,mid,L,R,val);
        update_range(id*2+1,mid+1,r,L,R,val);
        ST[id]=min(ST[id*2],ST[id*2+1]);
    }

    void update_pos(int id,int l,int r,int pos,ll val)
    {
        dolazy(id,l,r);
        if(l>pos||r<pos) return ;
        if(l==r)
        {
            ST[id]=min(ST[id],1ll*val);
            return ;
        }
        int mid=(l+r)/2;
        update_pos(id*2,l,mid,pos,val);
        update_pos(id*2+1,mid+1,r,pos,val);
        ST[id]=min(ST[id*2],ST[id*2+1]);
    }

    ll get (int id,int l,int r,int L,int R)
    {
        dolazy(id,l,r);
        if (r<L||R<l) return 1e18;
        if (L<=l&&r<=R) return ST[id];
        int mid=(l+r)/2;
        return min(get (id*2,l,mid,L,R),get (id*2+1,mid+1,r,L,R));
    }
}ST1,ST2;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n+m-1;i++) cin>>a[i];
    for(int i=1;i<=n+m-1;i++) cin>>b[i];
    vector<pii>pointL,pointR;
    for(int i=m;i>=1;i--) pointL.push_back(mp(1,i));
    for(int i=2;i<=n;i++) pointL.push_back(mp(i,1));
    for(int i=1;i<=n;i++) pointR.push_back(mp(i,m));
    for(int i=m-1;i>=1;i--) pointR.push_back(mp(n,i));
    for(int i=0;i<n+m-1;i++)
    {
        l[i+1]=pointL[i].fi+pointL[i].se-1;
        r[i+1]=pointR[i].fi+pointR[i].se-1;
        //cout<<l[i]<<' '<<r[i]<<'\n';
    }
    vector<int>order;
    for(int i=1;i<=n+m-1;i++) if(i%2==0) order.push_back(b[i]);
    for(int i=1;i<=n+m-1;i++)
    {
        if(l[i]%2==0)
        {
            l[i]/=2;
            r[i]/=2;
        }
        else
        {
            l[i]=(l[i]+1)/2+order.size();
            r[i]=(r[i]+1)/2+order.size();

        }
    }
    for(int i=1;i<=n+m-1;i++) if(i%2) order.push_back(b[i]);
    for(int i=1;i<=n+m-1;i++) b[i]=order[i-1];
    /*
    for(int i=1;i<=n+m-1;i++) cout<<b[i]<<' ';
    cout<<'\n';
    for(int i=1;i<=n+m-1;i++) cout<<l[i]<<' '<<r[i]<<'\n';
    */
    for(int i=1;i<=n+m-1;i++) val[i]={a[i],l[i],r[i]};
    n=n+m-1;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
    sort(val+1,val+n+1,lf);
    /*cout<<'\n';
    for(int i=1;i<=n;i++) cout<<val[i].a<<' '<<val[i].l<<' '<<val[i].r<<'\n';
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';
    cout<<'\n';*/
    ST1.update_range(1,0,n,1,n,1e16);
    ST2.update_range(1,0,n,1,n,1e16);
    for(int i=0;i<n;i++)
    {
        int curL=val[i+1].l;
        int curR=val[i+1].r;
        ll mn=ST1.get(1,0,n,0,curL-1);
        ll in_range_mn=ST2.get(1,0,n,curL,curR);
        ///chose a[i]
        ST1.update_range(1,0,n,0,curR,val[i+1].a);
        ST2.update_range(1,0,n,0,curR,val[i+1].a);
        /// not chose a[i]
        /// type 1:
        ST1.update_pos(1,0,n,curR,mn+s[curR]-s[curL-1]);
        ST2.update_pos(1,0,n,curR,mn-s[curL-1]);
        /// type2:
        ST1.update_pos(1,0,n,curR,in_range_mn+s[curR]);
        ST2.update_pos(1,0,n,curR,in_range_mn);
        //cout<<ST1.get(1,0,n,2,2)<<' '<<ST1.get(1,0,n,6,6)<<'\n';
    }
    cout<<ST1.get(1,0,n,0,n);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20