Submission #1230394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230394		DangKhoizzzz	Snowball (JOI21_ho_t2)	C++20	100 / 100	2039 ms	17776 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr4 array <int , 4>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;

int n , q , a[maxn] , L[maxn] , R[maxn] , ansL[maxn] , ansR[maxn] , b[maxn] , x[maxn];

priority_queue <arr4 , vector <arr4> , greater <arr4>> Q;

void check1()
{
    int dis = 0 , mx = 0;
    for(int i = 1; i <= q; i++)
    {
        dis += b[i];
        if(dis < 0) mx = max(mx , dis*-1);
        else
        {
            while(!Q.empty() && Q.top()[0] <= dis)
            {
                int w = Q.top()[1];
                int mid = Q.top()[2];
                int id = Q.top()[3];
                Q.pop();
                if(w <= mx)
                {
                    ansL[id] = w;
                    R[id] = mid - 1;
                }
                else L[id] = mid + 1;
            }
        }
    }
    while(!Q.empty())
    {
        int id = Q.top()[3] , mid = Q.top()[2] , w = Q.top()[1];
        if(w <= mx)
        {
            ansL[id] = w;
            R[id] = mid - 1;
        }
        else L[id] = mid + 1;
        Q.pop();
    }
}

void check2()
{
    int dis = 0 , mx = 0;
    for(int i = 1; i <= q; i++)
    {
        dis += b[i];
        if(dis >= 0) mx = max(mx , dis);
        else
        {
            while(!Q.empty() && Q.top()[0] <= dis*-1)
            {
                int w = Q.top()[1];
                int mid = Q.top()[2];
                int id = Q.top()[3];
                Q.pop();
                if(w <= mx)
                {
                    ansR[id] = w;
                    L[id] = mid + 1;
                }
                else R[id] = mid - 1;
            }
        }
    }

    while(!Q.empty())
    {
        int id = Q.top()[3] , mid = Q.top()[2] , w = Q.top()[1];
        if(w <= mx)
        {
            ansR[id] = w;
            L[id] = mid + 1;
        }
        else R[id] = mid - 1;
        Q.pop();
    }
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 1; i <= q; i++) cin >> b[i];

    x[0] = -INF;
    x[n+1] = INF;

    for(int i = 1; i <= n; i++) L[i] = x[i-1] , R[i] = x[i] , ansL[i] = 0;

    for(int _ = 0; _ <= 62; _++)
    {
        while(!Q.empty()) Q.pop();
        for(int i = 1; i <= n; i++)
        {
            if(L[i] <= R[i])
            {
                int mid = (L[i] + R[i])/2;
                //cout << L[i] << ' ' << R[i] << ' ' << mid << '\n';
                Q.push({mid - x[i-1] + 1 , x[i] - mid , mid , i});
            }
        }
        check1();
    }

    for(int i = 1; i <= n; i++) L[i] = x[i] , R[i] = x[i+1] , ansR[i] = 0;

    for(int _ = 0; _ <= 62; _++)
    {
        while(!Q.empty()) Q.pop();
        for(int i = 1; i <= n; i++)
        {
            if(L[i] <= R[i])
            {
                int mid = (L[i] + R[i])/2;
                Q.push({x[i+1] - mid + 1 , mid - x[i] , mid , i});
            }
        }
        check2();
    }



    for(int i = 1; i <= n; i++) cout << ansR[i] + ansL[i] << '\n';

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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