Submission #534334

#	Time	Username	Problem	Language	Result	Execution time	Memory
534334		Biaz	Snowball (JOI21_ho_t2)	C++17	100 / 100	341 ms	18452 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define X first
#define Y second
#define ist insert
#define pii pair<int,int>
typedef long long ll;
//typedef pair<int,int> pii;
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
const int INF=1700000000000000000;//2147483647;
const int MOD=998244353;//1000000007;
const int N=200005;
struct BIT{
    int n;
    vector<int> bit;
    void init(int _n){
        n=_n;
        bit.resize(n+5,0);
    }
    void add(int i,int v){
        while (i<=n){
            bit[i]+=v;
            i+=(i&-i);
        }
    }
    int que(int i){
        int res=0;
        while (i>0){
            res+=bit[i];
            i-=(i&-i);
        }
        return res;
    }
};
int n,Q;
int a[N],w[N],res[N];
pii d[N];
int mxL,mxR;
int search(int val){
    int l=1,r=n+1,res=0;
    while (r>=l){
        int mid=(l+r)/2;
        if (d[mid].fi>=val){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return res;
}

void sol(){
    cin >>n>>Q;
    for (int i=1;i<=n;i++)
        cin >>a[i];
    a[0]=-INF;a[n+1]=INF;
    for (int i=1;i<=Q;i++)
        cin >>w[i];
    BIT tr[2];tr[0].init(n+5);tr[1].init(n+5);
    for (int i=1;i<=n+1;i++)
        d[i].fi=a[i]-a[i-1],d[i].se=i;
    sort(d+1,d+n+2,greater<pii>());
    /*for (int i=1;i<=n+1;i++)
        cout <<d[i].se<<' ';
    cout <<"\n";*/
    int cur=0,r=n+1;
    mxL=mxR=0;
    for (int xx=1;xx<=Q;xx++){
        cur+=w[xx];
        if (mxL<=cur&&cur<=mxR) continue;
        if (cur>0){
            int loc=search(cur-mxL);
            //cout <<loc<<'\n';
            tr[1].add(1,cur-mxR);
            tr[1].add(loc+1,mxR-cur);
            while (d[r].fi<cur-mxL){
                tr[1].add(r,d[r].fi-(mxR-mxL));
                tr[1].add(r+1,-(d[r].fi-(mxR-mxL)));
                r--;
            }
        }
        if (cur<0){
            int loc=search(mxR-cur);
            //cout <<loc<<'\n';
            tr[0].add(1,mxL-cur);
            tr[0].add(loc+1,cur-mxL);
            while (d[r].fi<mxR-cur){
                tr[0].add(r,d[r].fi-(mxR-mxL));
                tr[0].add(r+1,-(d[r].fi-(mxR-mxL)));
                r--;
            }
        }
        mxL=min(mxL,cur);
        mxR=max(mxR,cur);
        /*for (int i=0;i<=n+2;i++)
            cout <<tr[1].que(i)<<' ';
        cout <<"\n";
        for (int i=0;i<=n+2;i++)
            cout <<tr[0].que(i)<<' ';
        cout <<"\n";*/

    }
    for (int i=1;i<=n+1;i++)
        res[d[i].se]+=tr[0].que(i);
    for (int i=1;i<=n+1;i++)
        res[d[i].se-1]+=tr[1].que(i);
    for (int i=1;i<=n;i++)
        cout <<res[i]<<'\n';
}
/*
4 3
-2 3 5 8
2
-4
7
*/
signed main()
{
    int _=1;
    //cin >>_;
    while (_--) sol();
    return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67