Submission #757580

#	Time	Username	Problem	Language	Result	Execution time	Memory
757580		Niko_shmiko	Snowball (JOI21_ho_t2)	C++17	100 / 100	111 ms	16832 KiB

Main

#include<bits/stdc++.h>
using namespace std;

long long n, q, cur, pre;

inline long long ch(long long a){
    return a/2+a%2;
}

struct Inter{
    long long len;
    long long rg;
    long long lg;
};

struct Day{
    long long lg=0;
    long long rg=0;
    long long bp=0;
};

int main(){
    scanf("%lld%lld%lld", &n, &q, &cur);
    Day p[q+1];
    Inter a[n-1];
    p[0].rg=0;
    p[0].lg=0;
    p[0].bp=0;
    for(long long i=0; i<n-1; i++){
        pre=cur;
        scanf("%lld", &cur);
        a[i].len=cur-pre;
    }
    for(long long i=1; i<=q; i++){
        scanf("%lld", &cur);
        p[i]=p[i-1];
        p[i].bp+=cur;
        p[i].lg=max(p[i].lg, p[i].bp);
        p[i].rg=max(p[i].rg, -p[i].bp);
    }
    // for(long long i=0; i<=q; i++){
    //     printf("day: %lld; left got: %lld; right got: %lld; ball is at :%lld\n", i, p[i].lg, p[i].rg, p[i].bp);
    // }
    for(long long i=0; i<n-1; i++){
        pre=0;
        cur=q;
        while(pre!=cur){
            if(p[ch(pre+cur)].lg+p[ch(pre+cur)].rg<=a[i].len){
                pre=ch(pre+cur);
            }else{
                cur=ch(pre+cur)-1;
            }
        }
        // printf("interval: %lld; day: %lld\n", i, pre);
        a[i].rg=p[pre].rg;
        a[i].lg=p[pre].lg;
        if(pre==q){
            continue;
        }
        if(p[pre+1].bp-p[pre].bp>0){
            a[i].lg=a[i].len-a[i].rg;
        }else{
            a[i].rg=a[i].len-a[i].lg;
        }
    }
    // for(long long i=0; i<n-1; i++){
    //     printf("itnerval: %lld; size: %lld; right got: %lld; left got :%lld\n", i, a[i].len, a[i].rg, a[i].lg);
    // }
    for(long long i=0; i<n; i++){
        pre=0;
        if(i==0){
            pre+=p[q].rg;
        }else{
            pre+=a[i-1].rg;
        }
        if(i==n-1){
            pre+=p[q].lg;
        }else{
            pre+=a[i].lg;
        }
        printf("%lld\n", pre);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%lld%lld%lld", &n, &q, &cur);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld", &cur);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%lld", &cur);
      |         ~~~~~^~~~~~~~~~~~~~

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