oj.uz

Submission #535702

# Submission time Handle Problem Language Result Execution time Memory
535702 2022-03-11T01:20:14 Z sam571128 Snowball (JOI21_ho_t2) C++17
33 / 100
 2 ms 596 KB 
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e3+5;
int arr[N], mn[N], mx[N], ans[N], ask[N];
int now = 0;

signed main(){
    fastio
    int n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> arr[i];
    }

    for(int i = 1;i <= q;i++){
        cin >> ask[i];
        now += ask[i];
        mn[i] = min(mn[i-1],now);
        mx[i] = max(mx[i-1],now);
    }

    ans[1] -= mn[q], ans[n] += mx[q];

    for(int i = 1;i <= n-1;i++){
        int dis = arr[i+1]-arr[i];
        int l = 0, r = q;
        while(l < r){
            int mid = (l+r+1)>>1;
            if(mx[mid]-mn[mid] <= dis) l = mid;
            else r = mid-1;
        }   

        ans[i] += mx[l], ans[i+1] -= mn[l];

        if(l != q){
            if(ask[l+1]>0){
                ans[i] += dis-(mx[l]-mn[l]);
            }else{
                ans[i+1] += dis-(mx[l]-mn[l]);
            }
        }
    }

    for(int i = 1;i <= n;i++){
        cout << ans[i] << "\n";
    }
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Runtime error 1 ms 596 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -