Submission #689730

#	Time	Username	Problem	Language	Result	Execution time	Memory
689730		prairie2022	Snowball (JOI21_ho_t2)	C++17	100 / 100	113 ms	15548 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define p pair<int, int>
#define f first
#define s second
using namespace std;


signed main(){
    fastio
    int n, q, l=0, r=0, cur=0, w;
    cin >> n >> q;
    vector<pair<int, p>> x(n);
    vector<p> y;
    auto it=y.begin();
    for(int i=0; i<n; i++){
        cin >> x[i].f;
    }
    for(int i=0; i<q; i++){
        cin >> w;
        cur += w;
        if(w>0 && cur>r){
            r = cur;
            y.push_back(make_pair(r-l, l-1));
        }
        if(w<0 && cur<l){
            l = cur;
            y.push_back(make_pair(r-l, r+1));
        }
    }
    /*for(const auto &c: y){
        cout << c.f << ' ' << c.s << '\n';
    }*/
    x[0].s.f = l;
    x[n-1].s.s = r;
    for(int i=1; i<n; i++){
        it = lower_bound(y.begin(), y.end(), make_pair(x[i].f-x[i-1].f, 0ll));
        if(it==y.end()){
            x[i-1].s.s = r;
            x[i].s.f = l;
        }
        else if(it->s>0){
            x[i-1].s.s = it->s-1;
            x[i].s.f = x[i-1].s.s-x[i].f+x[i-1].f;
        }
        else{
            x[i].s.f = it->s+1;
            x[i-1].s.s = x[i].f-x[i-1].f+x[i].s.f;
        }
    }
    for(int i=0; i<n; i++){
        cout << x[i].s.s-x[i].s.f << '\n';
    }
    return 0;
}

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