Submission #1310778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310778		aryan	Snowball (JOI21_ho_t2)	C++20	33 / 100	2595 ms	4608 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,q;
    cin >> n >> q;
    vector<i64> a(n);
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }

    vector<i64> dist(n - 1);
    for(int i = 0;i < n - 1;i++){
        dist[i] = a[i + 1] - a[i];
    }

    // |...|...|...|
    vector<pair<i64,int>> que;
    i64 cur = 0;
    for(int i = 0;i < q;i++){
        i64 w;
        cin >> w;
        cur += w;
        que.push_back({cur,i});
    }
    // sort(que.begin(),que.end());

    vector<i64> we(n);
    for(int i = 0;i < n;i++){

        // right
        {
            function<bool(i64,i64)> f = [&](i64 x,i64 d){
                bool ok = false;
                int mini = q;
                for(int i = 0;i < q;i++){
                    if(que[i].first > 0LL && x <= que[i].first){
                        mini = min(mini,que[i].second);
                        ok = true;
                    }
                }
                if(!ok) return false;
                for(int i = 0;i < q;i++){
                    if(que[i].first < 0LL && x - que[i].first > d && que[i].second < mini){
                        return false;
                    }
                }
                return true;
            };
            i64 d = ((i != n - 1) ? dist[i] : (i64)1e15);
            i64 s = 0;
            i64 e = d;
            while(e > s){
                i64 mid = (s + e + 1LL) / 2;
                if(f(mid,d)){
                    s = mid;
                }else{
                    e = mid - 1;
                }
            }
            we[i] += e;
        }

        // left
         {
            function<bool(i64,i64)> f = [&](i64 x,i64 d){
                bool ok = false;
                int mini = q;
                for(int i = 0;i < q;i++){
                    if(que[i].first < 0LL && x <= -1LL*que[i].first){
                        mini = min(mini,que[i].second);
                        ok = true;
                    }
                }
                if(!ok) return false;
                for(int i = 0;i < q;i++){
                    if(que[i].first > 0LL && x + que[i].first > d && que[i].second < mini){
                        return false;
                    }
                }
                return true;
            };
            i64 d = ((i != 0) ? dist[i - 1] : (i64)1e15);
            i64 s = 0;
            i64 e = d;
            while(e > s){
                i64 mid = (s + e + 1LL) / 2;
                if(f(mid,d)){
                    s = mid;
                }else{
                    e = mid - 1;
                }
            }
            we[i] += e;
        }
    }
    for(int i = 0;i < n;i++){
            cout << we[i] << '\n';
    }

    return 0;
}

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