oj.uz

답안 #469321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469321 2021-08-31T13:18:20 Z vincent97198 Snowball (JOI21_ho_t2) C++14
0 / 100
 2 ms 332 KB 
#include<bits/stdc++.h>
#define int long long
#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=0;
    for(int i=0;i<Q.size();++i){
        TOTAL+=abs(Q[i]);
        if(Q[i]>0)
            POS=Q[i];
        else
            NEG=-Q[i];
        MAP[TOTAL]={POS,NEG};
    }

    int pre=0,ans=0;
    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{
            ans=pre+d[i]-pre_pair.second;
            pre=pre_pair.second;
        }

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

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

Compilation message

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

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -