Submission #465033

#	Time	Username	Problem	Language	Result	Execution time	Memory
465033		Deepesson	Snowball (JOI21_ho_t2)	C++17	100 / 100	315 ms	14016 KiB

Main

#include <bits/stdc++.h>
///Bola de neve
#define MAX 2000005
long long valores[MAX][2];
bool dir[MAX];
int main()
{
    int N,Q;
    std::cin>>N>>Q;
    long long array[N];for(auto&x:array)std::cin>>x;
    for(auto&x:array) x += 1LL<<30LL;
    long long left=0,right=0,pos=0;
    for(int i=0;i!=Q;++i){
        long long D;
        std::cin>>D;
        pos+=D;
        if(pos<0){
            long long val = pos;
            if(val<0)val*=-1;
            left=std::max(left,val);
            dir[i]=true;
        }else {
            long long val = pos;
            if(val<0)val*=-1;
            right=std::max(right,val);
        }
        valores[i][0]=left;
        valores[i][1]=right;
    }
    long long resultados[N]={};
    resultados[0]+=left;
    resultados[N-1]+=right;
    for(int i=1;i!=N;++i){
        ///i-1 eh esquerda, se referindo a direita
        ///i eh a direita, e ira para a esquerda
        /// i-1 -> Direita     Esquerda <- i
        long long obj = array[i]-array[i-1];
        if(valores[Q-1][0]+valores[Q-1][1]>obj){
            int l=0,r=Q-1;
            while(l<r){
                int m = (l+r)/2;
                long long val = valores[m][0]+valores[m][1];
                if(val>=obj){
                    r=m;
                }else l=m+1;
            }

            long long a = valores[l][0]; ///Esquerda
            long long b = valores[l][1]; ///Direita
            if(a+b==obj){
                resultados[i-1]+=b;
                resultados[i]+=a;
            }else {
                long long dif = (a+b)-(obj);
                if(dir[l]){///Para a esquerda
                    a-=dif;
                }else {///Para a direita
                    b-=dif;
                }
                resultados[i-1]+=b;
                resultados[i]+=a;
            }

        }else {
            resultados[i-1]+=right;
            resultados[i]+=left;
        }
    }
    for(auto&x:resultados)std::cout<<x<<"\n";
}

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