oj.uz

Submission #1000926

# Submission time Handle Problem Language Result Execution time Memory
1000926 2024-06-18T11:25:46 Z vjudge1 Safety (NOI18_safety) C++17
0 / 100
 20 ms 4656 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -