oj.uz

Submission #871098

# Submission time Handle Problem Language Result Execution time Memory
871098 2023-11-09T21:55:47 Z Maite_Morale Snowball (JOI21_ho_t2) C++14
0 / 100
 3 ms 6608 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>

ll n,q,a[MAX],qry[MAX],mx[MAX],mn[MAX];
ll bs(ll x){
    ll p=0,f=q;//cout<<x;
    while(abs(p-f)!=1){
        ll m=(p+f)/2;//cout<<m<<" "<<mx[m]<<"+"<<-mn[m]<<"\n";
        if(mx[m]-mn[m]>x)f=m;
        else             p=m;
    }
return p;
}
int main(){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<q;i++){
        cin>>qry[i];
        if(i==0){
            mx[i]=max((ll)0,qry[i]);
            mn[i]=min((ll)0,qry[i]);
            continue;
        }qry[i]+=qry[i-1];
        mx[i]=max(mx[i-1],qry[i]);
        mn[i]=min(mn[i-1],qry[i]);
    }
    for(int i=0;i<n;i++){
        ll r=0;
        if(i==0)r+=-mn[q-1];
        else{
            ll x=bs(a[i]-a[i-1]);//cout<<x<<" ";
            if(x==q-1)r+=-mn[q-1];
            else     if(-mn[x]<-mn[x+1])r+=a[i]-a[i-1]-mx[x];
                     else               r+=-mn[x];
        }//cout<<r<<" ";
        if(i==n-1)r+=mx[q-1];
        else{
            ll x=bs(a[i+1]-a[i]);//cout<<x<<" ";
            if(x==q-1)r+=mx[q-1];
            else     if(mx[x]<mx[x+1])r+=a[i+1]-a[i]+mn[x];
                     else             r+=mx[x];
        }cout<<r<<"\n";
    }

return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6608 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Incorrect 2 ms 6492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6608 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Incorrect 2 ms 6492 KB Output isn't correct
15 Halted 0 ms 0 KB -