Submission #469335

#	Time	Username	Problem	Language	Result	Execution time	Memory
469335		vincent97198	Snowball (JOI21_ho_t2)	C++14	100 / 100	345 ms	19380 KiB

Main

#include<bits/stdc++.h>
#define int int64_t
#define double long double
using namespace std;

const double eps=1e-6;

int32_t main()
{
    int n,q;  cin >> n >> q;

    vector<int> pos(n),d(n,1e18);
    for(int i=0;i<n;++i)    cin >> pos[i];
    for(int i=0;i<n-1;++i)    d[i]=abs(pos[i+1]-pos[i]);

    vector<int> Q;
    int tmp,tmp_now=0,POS_MAX=0,NEG_MIN=0;
    for(int i=0;i<q;++i){
        cin >> tmp;
        tmp_now+=tmp;
        if(tmp_now>=0 && tmp_now>POS_MAX){
            if(!Q.empty() && Q.back()>=0 && tmp_now>Q.back())   Q.pop_back();
            Q.emplace_back(tmp_now);
        }
        if(tmp_now<0 && tmp_now<NEG_MIN){
            if(!Q.empty() && Q.back()<=0 && tmp_now<Q.back())    Q.pop_back();
            Q.emplace_back(tmp_now);
        }

        POS_MAX=max(POS_MAX,tmp_now);
        NEG_MIN=min(NEG_MIN,tmp_now);
    }

    map<int,pair<int,int>> MAP;
    MAP[0]={0,0};
    int POS=0, NEG=0,TOTAL;
    for(int i=0;i<Q.size();++i){
        if(Q[i]>0)
            POS=Q[i];
        else
            NEG=-Q[i];
        TOTAL=NEG+POS;
        MAP[TOTAL]={POS,NEG};
    }
    MAP[1e18]={1e18,1e18};

    int pre=0,ans;
    for(int i=0;i<n;++i){
        if(i==0)
            pre=-NEG_MIN;
        if(i==n-1){
            pre+=POS_MAX;
            cout << pre << '\n';
            break;
        }

        pair<int,int> now_pair=MAP.upper_bound(d[i])->second,pre_pair=prev(MAP.upper_bound(d[i]))->second;
        if(now_pair.first==pre_pair.first){
            ans=pre+pre_pair.first;
            pre=d[i]-pre_pair.first;
        }
        else if(now_pair.second==pre_pair.second){
            ans=pre+d[i]-pre_pair.second;
            pre=pre_pair.second;
        }
        else{
            ans=pre+pre_pair.first;
            pre=pre_pair.second;
        }

        cout << ans << '\n';
    }

    return 0;
}
/*
4 3
-2 3 5 8
2
-4
7

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
 */

Compilation message (stderr)

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

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