oj.uz

Submission #387534

# Submission time Handle Problem Language Result Execution time Memory
387534 2021-04-08T18:54:33 Z wildturtle Snowball (JOI21_ho_t2) C++17
100 / 100
 274 ms 13932 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,A[500005],B[500005],maxx[500005],minn[500005],ans,r,le,ri,mid,idx;
ll gadakveta(ll x,ll y) {
    le=1; ri=m; ans=-1;
    while(le<=ri) {
        mid=(le+ri)/2;
        if(A[x]+maxx[mid]>=A[y]+minn[mid]) { ri=mid-1; ans=mid; }
        else le=mid+1;
    }
    //if(x==5 && y==6) cout<<"("<<ans<<")";
    idx=min(max(A[x]+maxx[ans],A[y]+minn[ans]),max(A[x]+maxx[ans-1],A[y]+minn[ans-1]));
    return idx;
}
int main() {
    cin>>n>>m;
    for(ll i=1;i<=n;i++) {
        cin>>A[i];
    }
    maxx[0]=a; minn[0]=a;
    for(ll i=1;i<=m;i++) {
        cin>>B[i];
        a+=B[i];
        maxx[i]=max(maxx[i-1],a);
        minn[i]=min(minn[i-1],a);
    }
    //cout<<minn[m]<<" "<<maxx[m]<<endl;
    for(ll i=1;i<=n;i++) {
        if(i==1) l=A[i]+minn[m];
        if(i==n) r=A[i]+maxx[m];
        if(i!=1) { if(A[i-1]+maxx[m]<=A[i]+minn[m]) l=A[i]+minn[m]; else l=gadakveta(i-1,i); }
        if(i!=n) { if(A[i]+maxx[m]<=A[i+1]+minn[m]) r=A[i]+maxx[m]; else r=gadakveta(i,i+1); }
        cout/*<<l<<" "<<r<<" "*/<<r-l<<" ";
    }
}

Subtask #1
33.0 / 33.0

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

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 3 ms 492 KB Output is correct
17 Correct 3 ms 492 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 3 ms 492 KB Output is correct
20 Correct 95 ms 7148 KB Output is correct
21 Correct 89 ms 7020 KB Output is correct
22 Correct 81 ms 6764 KB Output is correct
23 Correct 77 ms 6636 KB Output is correct
24 Correct 91 ms 6996 KB Output is correct
25 Correct 264 ms 12032 KB Output is correct
26 Correct 263 ms 11884 KB Output is correct
27 Correct 251 ms 11500 KB Output is correct
28 Correct 268 ms 11728 KB Output is correct
29 Correct 251 ms 11244 KB Output is correct
30 Correct 240 ms 10604 KB Output is correct
31 Correct 181 ms 9964 KB Output is correct
32 Correct 166 ms 10348 KB Output is correct
33 Correct 26 ms 1516 KB Output is correct
34 Correct 274 ms 12396 KB Output is correct
35 Correct 260 ms 11884 KB Output is correct
36 Correct 268 ms 12140 KB Output is correct
37 Correct 259 ms 11884 KB Output is correct
38 Correct 255 ms 11628 KB Output is correct
39 Correct 258 ms 11884 KB Output is correct
40 Correct 213 ms 11756 KB Output is correct
41 Correct 110 ms 7788 KB Output is correct
42 Correct 165 ms 10092 KB Output is correct
43 Correct 264 ms 13548 KB Output is correct
44 Correct 109 ms 7660 KB Output is correct
45 Correct 190 ms 11628 KB Output is correct
46 Correct 255 ms 13548 KB Output is correct
47 Correct 262 ms 13804 KB Output is correct
48 Correct 265 ms 13932 KB Output is correct