제출 #671673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671673		hail	Snowball (JOI21_ho_t2)	C++17	100 / 100	122 ms	16972 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
using ll= long long;
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define inpint(x) int x; cin>>x
#define inpll(x) long long x; cin>>x
#define fl(i, n) for(int i=0; i<n; i++)
#define flo(i, n) for(int i=1; i<=n; i++)
#define int long long 
#define pi pair<int, int>
#define mp make_pair
#define ld long double

const int MODa = 7 + (int)1e9;
const int INF = (int)1e18;
const int MOD = 998244353;

void solve()
{
    int n, q;
    cin>>n>>q;

    vector<int> x(n+1, 0);
    for(int i=1; i<=n; i++)
    {
        cin>>x[i];
    }

    vector<int> w(q+1, 0);
    vector<int> a(q+1, 0);
    vector<int> ml(q+1, 0);
    vector<int> mr(q+1, 0);
    for(int i=1; i<=q; i++)
    {
        cin>>w[i];
        a[i] = a[i-1] + w[i];
        ml[i] = min(ml[i-1], a[i]);
        mr[i] = max(mr[i-1], a[i]);
    }

    vector<int> ans(n+1, 0);
    ans[1] -= ml[q];
    ans[n] += mr[q];
    for(int i=1; i<n; i++)
    {
        int j = i+1;
        if(x[i]+mr[q]<=x[j]+ml[q])
        {
            ans[i] += mr[q];
            ans[j] -= ml[q];
            continue;
        }

        int high = q;
        int low = 0;
        //cerr<<i<<": \n";
        while(high-low>1)
        {
            int mid = (high+low)/2;
            if(x[i]+mr[mid]>x[j]+ml[mid]) high = mid;
            else low = mid;
            //cerr<<low<<" "<<high<<"\n";
        }
        //cerr<<"\n";

        ans[i] += mr[low];
        ans[j] -= ml[low];
        if(w[low+1]<0)
        {
            ans[j] += x[j] - x[i] - mr[low] + ml[low];
        }
        else
        {
            ans[i] += x[j] - x[i] - mr[low] + ml[low];
        }
    }

    for(int i=1; i<=n; i++)
    {
        cout<<ans[i]<<"\n";
    }
}

signed main()
{
    fast_io;
     
    int t=1; 
    //cin>>t;
    while(t--)
    {
        solve();
    }
    cout<<endl;
}

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