Submission #846577

#	Time	Username	Problem	Language	Result	Execution time	Memory
846577		yangjl	Safety (NOI18_safety)	C++17	100 / 100	82 ms	11184 KiB

safety

#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
#define ALL(a) a.begin(),a.end()
using namespace std;
using ll=long long;

constexpr int N = 2e5 + 10;
int n;
ll h,a[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>n>>h;
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
    }

    priority_queue<ll> q1;
    priority_queue<ll,vector<ll>,greater<>> q2;
    ll d1=0,d2=0;
    ll k=1,b=-a[1];// kx+b
    q1.push(a[1]);
    q2.push(a[1]);

    for(int i=2; i<=n; ++i) {
        // x-h,x+h
        d1-=h;
        d2+=h;
        b-=k*h;
        // f(x) = g_i-1(x)+|x-a[i]|
        k+=1;
        b-=a[i];
        ll l=q1.top()+d1;
        ll r=q2.top()+d2;
        if(l<=a[i] && a[i] <=r) {
            q1.push(a[i]-d1);
            q2.push(a[i]-d2);
        }else if(a[i]<l) {
            // l处 0 -> 1
            q2.push(l-d2);
            q1.pop();
            q1.push(a[i]-d1);
            q1.push(a[i]-d1);
        }else {
            // r处 -1 -> 0
            q1.push(r-d1);
            q2.pop();
            q2.push(a[i]-d2);
            q2.push(a[i]-d2);
        }
        // debug(q1);
    }

    // 还原 k=0 处的直线
    while(q2.size()) {
        q1.push(q2.top()+d2-d1);
        q2.pop();
    }

    debug(k,b);

    while(k) {
        ll x=q1.top()+d1;
        q1.pop();
        b=x+b;
        k--;
        debug(x,k,b);
        if(!k) {
            cout<<k*x+b;
            break;
        }
    }
    return 0;
}
/*




*/

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:23:23: warning: statement has no effect [-Wunused-value]
   23 | #define debug(args...)0
      |                       ^
safety.cpp:83:5: note: in expansion of macro 'debug'
   83 |     debug(k,b);
      |     ^~~~~
safety.cpp:23:23: warning: statement has no effect [-Wunused-value]
   23 | #define debug(args...)0
      |                       ^
safety.cpp:90:9: note: in expansion of macro 'debug'
   90 |         debug(x,k,b);
      |         ^~~~~

• 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