Submission #598553

#	Time	Username	Problem	Language	Result	Execution time	Memory
598553		KarolZ	Snowball (JOI21_ho_t2)	C++14	100 / 100	166 ms	21912 KiB

Main

//Karol Zeleznik
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
pair<ll,ll>t[200010];
//to co odejmuje
vector<ll>v;
//wejscie
priority_queue< pair<ll,ll> >p;
priority_queue< pair<ll,ll> >l;
//kolejki minimalne roznice na prawo i na lewo
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
    ll n,q,v1,akt=0,mnl=0,mnp=0,as;
    // n,q,v1,aktualna pozycja,max na lewo i prawo
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>v1;
        v.push_back(v1);
        t[i].first=1e18;
        t[i].second=1e18;
    }
    for(int i=0;i<v.size();i++){
        if(i!=n-1)p.push({-v[i+1]+v[i],i});
        if(i!=0)l.push({-v[i]+v[i-1],i});
    }
    p.push({-1e18,n-1});
    l.push({-1e18,0});
    while(q--){
        cin>>v1;
        akt+=v1;
        //cout<<akt<<'\n';
        if(akt>mnp){
            while(-p.top().first+mnl<akt){
                t[p.top().second].second=max(mnp,-p.top().first+mnl);
                //cout<<-p.top().first+mnl<<'\n';
                p.pop();
            }
            mnp=akt;
        }
        if(akt<mnl){
            while(-l.top().first-mnp<-akt){
                t[l.top().second].first=max(-mnl,-l.top().first-mnp);
                //cout<<t[l.top().second].first<<'\n';
                l.pop();
            }
            mnl=akt;
        }
    }
    //cout<<"\ndla 3 odp to: "<<t[2].first<<" + "<<t[2].second<<'\n';
    for(int i=0;i<n;i++){
        as=0;
        if(t[i].first==1e18)as-=mnl;
        else as+=t[i].first;
        if(t[i].second==1e18)as+=mnp;
        else as+=t[i].second;
        cout<<as<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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