Submission #425458

#	Time	Username	Problem	Language	Result	Execution time	Memory
425458		errorgorn	Safety (NOI18_safety)	C++17	100 / 100	41 ms	5452 KiB

safety

#include <cstdio>
#include <queue>
using namespace std;
int n;
long long h;
long long t;
priority_queue<long long> lower;
priority_queue<long long,vector<long long>,greater<long long> > upper;
inline void read(int& x) {
    x = 0;
    char ch = getchar_unlocked();
    while (ch&16){ //this will break when ‘\n’ or ‘ ‘ is encountered
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar_unlocked();
	}
}
inline void read(long long& x) {
    x = 0;
    char ch = getchar_unlocked();
    while (ch&16){ //this will break when ‘\n’ or ‘ ‘ is encountered
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar_unlocked();
	}
}
int main(){
    read(n),read(h);
    read(t);
    lower.push(t);
    upper.push(t);
    long long ans=0;
    long long offset;
    for (int x=1;x<n;x++){
        offset=x*h;
        read(t);
        if (!lower.empty() && t<lower.top()-offset){ ///lower part
            ans+=(lower.top()-offset)-t;
            lower.push(t+offset);
            lower.push(t+offset);
            upper.push(lower.top()-offset*2);
            lower.pop();
        }
        else if (!upper.empty() && upper.top()+offset<t){ ///upper part
            ans+=t-(upper.top()+offset);
            upper.push(t-offset);
            upper.push(t-offset);
            lower.push(upper.top()+offset*2);
            upper.pop();
        }
        else{
            lower.push(t+offset);
            upper.push(t-offset);
        }
        //printf("%lld %lld %lld\n",ans,lower.top()-offset,upper.top()+offset);
    }
    printf("%lld\n",ans);
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29