oj.uz

Submission #974289

# Submission time Handle Problem Language Result Execution time Memory
974289 2024-05-03T07:31:19 Z berr Snowball (JOI21_ho_t2) C++17
0 / 100
 1 ms 532 KB 
#include <bits/stdc++.h>
using namespace std; 
#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int n, q; cin >> n >> q;

    vector<int> x(n), l(n), r(n);
    vector<int> mi(q), ma(q);

    for(auto &i: x) cin >> i;
    vector<int> op(q);

    for(int i=0; i<q; i++) cin >> op[i];

    for(int i=1; i<q; i++){
        op[i]+=op[i-1];
        mi[i]=mi[i-1]; ma[i] =ma[i-1];

        if(op[i] < op[mi[i]]) mi[i]=i;
        if(op[i] > op[ma[i]]) ma[i]=i;
    }

    l[0]=x[0]+op[mi[q-1]]; r[n-1] = x[n-1]+op[ma[q-1]];

    for(int i=0; i<n-1; i++){
        int s=-1;

        for(int l=20; l>=0; l--){
            int tmp = s+(1<<l);
            if(tmp >= q-1) continue;
            if(op[ma[tmp]] - op[mi[tmp]]>=x[i+1]-x[i]) continue;
            s=tmp;
        }

        s++;
        
        if(x[i]+op[ma[s]]>=x[i+1]+op[mi[s]]){            
            if(ma[s] < mi[s]){
                r[i]=x[i]+op[ma[s]];
                l[i+1]=r[i];
            }
            else{
                l[i+1]=x[i+1]+op[mi[s]];
                r[i]=l[i+1];

            }
        }
        else{

            r[i]=min(x[i+1], x[i]+op[ma[s]]);
            l[i+1]=max(x[i+1]+op[mi[s]], x[i]);
        }
    }
    for(int i=0; i<n; i++){
        l[i]=min(l[i], x[i]);
        r[i]=max(r[i], x[i]);
    }

    for(int i=0; i<n; i++) cout<<r[i]-l[i]<<"\n";
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 532 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 532 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -