Submission #1000926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000926		vjudge1	Safety (NOI18_safety)	C++17	0 / 100	20 ms	4656 KiB

safety

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 2e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const int MOD = 1e9 + 7;
const int maxl = 14;

int n, h;
int a[maxn];
int sl, sr;
priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;

void addl(int x){l.push(x + sl);}
int topl(){return l.top() - sl;}
void shiftl(int x){sl += x;}

void addr(int x){r.push(x - sr);}
int topr(){return r.top() + sr;}
void shiftr(int x){sr += x;}

void out(){
	vector<int> v;
	while(l.size()){
		v.push_back(topl());
		l.pop();
	}
	for(int i = v.size() - 1; i >= 0; i--){
		cout << v[i] << ' ';
		addl(v[i]);
	}
	v.clear();
	while(r.size()){
		v.push_back(topr());
		r.pop();
	}
	cout << "| ";
	for(int i = 0; i < v.size(); i++){
		cout << v[i] << ' ';
		addr(v[i]);
	}
	cout << ent;
}

void test(){
    cin >> n >> h;
    for(int i = 1; i <= n ;i++){
        cin >> a[i];
    }
    addl(a[1]);
    addr(a[1]);
    shiftl(h);
    shiftr(h);
    // out();
    ll sum = 0;
    for(int i = 2; i <= n; i++){
    	if(a[i] < topl()){
    		sum += topl() - a[i];
    		addr(topl());
    		l.pop();
    		addl(a[i]);
    	} else if(a[i] > topr()){
    		sum += a[i] - topr();
    		addl(topr());
    		r.pop();
    		addr(a[i]);
    	} else{
    		addl(a[i]);
    		addr(a[i]);
    	}
    	shiftl(h);
    	shiftr(h);
    	// out();
    }
    cout << sum;
}

// 6 1
// 2 10 0 2 4 3

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; t = 1;
    while(t--) test();
    cout << ent;
}

Compilation message (stderr)

safety.cpp: In function 'void out()':
safety.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~

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