Submission #1155898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155898		dosts	Snowball (JOI21_ho_t2)	C++20	100 / 100	471 ms	8264 KiB

Main

//Siga Siga?! YES!
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e3+1,MOD =  998244353;

struct Query {
    int l,r,id;
};
void solve() {  
    int n,q;
    cin >> n >> q;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    vi ans(n+1,0);
    vi prefmn(q+2,0),prefmx(q+2,0);
    int s = 0;
    for (int i=1;i<=q;i++) {
        int x;
        cin >> x;
        s+=x;
        prefmn[i] = min(prefmn[i-1],s);
        prefmx[i] = max(prefmx[i-1],s);
    }
    prefmn[q+1] = prefmn[q];
    prefmx[q+1] = prefmx[q];
    ans[1]+=max(0ll,-prefmn[q]);
    ans[n]+=max(0ll,prefmx[q]);

    auto getpos = [&](int x) {
        int l = 0;
        int r = q;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (prefmx[m] >= x) r = m-1;
            else l = m+1;
        }
        return l;
    };
    for (int i=1;i<n;i++) {
        int ln = a[i+1]-a[i];
        if (max(0ll,prefmx[q])+max(0ll,-prefmn[q]) < ln) {
            ans[i]+=max(0ll,prefmx[q]);
            ans[i+1]+=max(0ll,-prefmn[q]);
            continue;
        }
        int l = 0;
        int r = ln;
        while (l<=r) {
            int m = (l+r) >> 1;
            //m sağa esme vakti ln-m+1 sola esma vaktinden önce mi?
            int t1 = getpos(m);
            if (prefmn[t1] > -(ln-m+1)) l = m+1;
            else r = m-1;
        }
        ans[i]+=r;
        ans[i+1]+=ln-r;
    }
    for (int i=1;i<=n;i++) cout << ans[i] << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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