Submission #1310793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310793		aryan	Snowball (JOI21_ho_t2)	C++20	33 / 100	1507 ms	11372 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<int> sm(q,q);
    for(int i = q - 1;i >= 0;i--){
        sm[i] = que[i].second;
        if(i + 1 < q) sm[i] = min(sm[i],sm[i + 1]);
    }
    vector<int> pm(q,q);
    for(int i = 0;i < q;i++){
        pm[i] = que[i].second;
        if(i != 0) pm[i] = min(pm[i],pm[i - 1]);
    }
    vector<i64> we(n);
    for(int i = 0;i < n;i++){

        // right
        {
            function<bool(i64,i64)> f = [&](i64 x, i64 d) {
                int ind = lower_bound(que.begin(), que.end(),pair<i64,int>{x, -1}) - que.begin();
            
                if (ind == q) return false;

                int ind2 = lower_bound(que.begin(), que.end(),pair<i64,int>{x - d, -1}) - que.begin() - 1;           
                if (ind2 < 0) return true;
                return pm[ind2] >= sm[ind];
            };

            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) {
                int ind = upper_bound(que.begin(), que.end(),pair<i64,int>{-x, INT_MAX}) - que.begin() - 1;                 
                if (ind < 0) return false;
                
                int ind2 = upper_bound(que.begin(), que.end(),pair<i64,int>{d - x, INT_MAX}) - que.begin();
                if (ind2 == q) return true;
                return sm[ind2] >= pm[ind];
        };

            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