oj.uz

Submission #736052

# Submission time Handle Problem Language Result Execution time Memory
736052 2023-05-05T07:18:20 Z Hydrolyzed Safety (NOI18_safety) C++14
5 / 100
 192 ms 20048 KB 
/*
 * AUTHOR	: Hydrolyzed~
 * SCHOOL	: RYW
 * TASK		: Safety
 * ALGO		: Slope Trick
 * DATE		: 5 May 2023
 * */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#ifndef _DEBUG
// @==== Libary ====@ //

// @================@ //
#endif

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

// @=== Debugger ===@ //
#ifdef _DEBUG
#include "debug.hpp"
#else
#define dbg(...) 0
#endif
// @================@ //

using ll = long long;

const int MxN = 200020;
ll a[MxN], h;

struct slope_trick{
	multiset<ll> ms_l, ms_r;
	ll min_y = 0, lz_l = 0, lz_r = 0;
	inline void add_line(ll value){
		// real_value = insert_value + lazy
		// insert_value = real_value - lazy
		lz_l -= h; lz_r += h;
		if(ms_l.empty() && ms_r.empty()){
			ms_l.emplace(value);
			ms_r.emplace(value);
		}	
		else if(value <= *ms_l.rbegin() + lz_l){
			min_y += (*ms_l.rbegin() + lz_l) - value;
			ms_r.emplace(*ms_l.rbegin() + lz_l - lz_r);
			ms_l.erase(--ms_l.end());
			ms_l.emplace(value - lz_l);
			ms_l.emplace(value - lz_l);
		}
		else if(value >= *ms_r.begin() + lz_r){
			min_y += value - (*ms_r.begin() + lz_r);
			ms_l.emplace(*ms_r.begin() + lz_r - lz_l);
			ms_r.erase(ms_r.begin());
			ms_r.emplace(value - lz_r);
			ms_r.emplace(value - lz_r);
		}
		else{
			ms_l.emplace(value - lz_l);
			ms_r.emplace(value - lz_r);
		}
	};
} dp;

inline void solution(){
	int n;
	cin >> n >> h;
	for(int i=1; i<=n; ++i){
		cin >> a[i];
	}
	for(int i=1; i<=n; ++i){
		dp.add_line(a[i]);
		dbg(dp.min_y);
	}
	cout << dp.min_y;
	return ;
}

signed main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);	
	int q = 1;
//	cin >> q;
	while(q--){
		solution();
		cout << "\n";
	}
	return 0;
}
// https://github.com/MasterIceZ/archive/tree/main/cpp-template

Compilation message

safety.cpp: In function 'void solution()':
safety.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define dbg(...) 0
      |                  ^
safety.cpp:79:3: note: in expansion of macro 'dbg'
   79 |   dbg(dp.min_y);
      |   ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 13684 KB Output is correct
2 Correct 192 ms 19400 KB Output is correct
3 Correct 181 ms 20048 KB Output is correct

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 324 KB Output isn't correct
8 Halted 0 ms 0 KB -