oj.uz

Submission #1102236

# Submission time Handle Problem Language Result Execution time Memory
1102236 2024-10-17T17:30:39 Z nhphuc Nile (IOI24_nile) C++17
0 / 100
 2000 ms 21408 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

void init (vector<int32_t> &a, vector<pair<int, int>> &b){
	vector<int32_t> tmp = a;
	for (int i = 0; i < b.size(); ++i)
		a[i] = tmp[b[i].second];
	return;
}

bool cmp (array<int, 3> a, array<int, 3> b){
	for (int i = 0; i < 3; ++i)
		if (a[i] < b[i])
			return true;
		else
			if (a[i] > b[i])
				return false;
	return true;
}

const int inf = 1e12;

vector<int> calculate_costs (
	vector<int32_t> w, vector<int32_t> a, 
	vector<int32_t> b, vector<int32_t> e
){
	int n = a.size(), q = e.size();
	set<int> st;
	vector<int> ans(q), c(n), sz(n); 
	vector<pair<int, int>> d(q), x(n);
	vector<array<int, 3>> eve, mn(n, {inf, inf, inf});
	for (int i = 0; i < n; ++i)
		x[i] = {w[i], i};
	for (int i = 0; i < q; ++i)
		d[i] = {e[i], i};
	sort(d.begin(), d.end());
	sort(x.begin(), x.end());
	init(a, x);
	init(b, x);
	init(w, x);
	int res = accumulate(b.begin(), b.end(), 0ll), add = 0;
	for (int i = 0; i < n; ++i){
		st.insert(i);
		c[i] = a[i] - b[i];
		sz[i] = 1;
		mn[i][i & 1] = c[i];
		add += c[i];
		if (i + 1 < n)
			eve.push_back({w[i + 1] - w[i], i, 0});
		if (i + 2 < n)
			eve.push_back({w[i + 2] - w[i], i, 1});
	}
	sort(eve.begin(), eve.end());

	auto fi = [&] (int i){
		return min(mn[i][i & 1], mn[i][2]) * (sz[i] & 1);
	};
	auto u1 = [&] (int i){
		int j = *prev(st.upper_bound(i));
		int k = i + 1;
		add -= (fi(j) + fi(k));
		st.erase(k);
		sz[j] += sz[k];
		for (int l = 0; l < 3; ++l)
			mn[j][l] = min(mn[j][l], mn[k][l]);
		add += fi(j);
	};
	auto u2 = [&] (int i){
		int j = *prev(st.upper_bound(i));
		add -= fi(j);
		mn[j][2] = min(mn[j][2], c[i]);
		add += fi(j);
	};
	int j = 0;
	for (auto [x, y] : d){
		while (j < eve.size() && eve[j][0] <= y){
			int i = eve[j][1];
			if (eve[j][2])
				u2(i);
			else
				u1(i);
		}
		ans[y] = res + add;
	}
	return ans;
}

// int32_t main (){
// 	#define task "test"
// 	if (fopen(task".inp", "r")){
// 	    freopen(task".inp", "r", stdin);
// 	    freopen(task".out", "w", stdout);
// 	}
// 	int n, q; cin >> n >> q;
// 	vector<int32_t> w(n), a(n), b(n), e(q);
// 	for (int32_t &x : w) cin >> x;
// 	for (int32_t &x : a) cin >> x;
// 	for (int32_t &x : b) cin >> x;
// 	for (int32_t &x : e) cin >> x;
// 	vector<int> ans = calculate_costs(w, a, b, e);
// 	for (int x : ans)
// 		cout << x << " ";
// }

Compilation message

nile.cpp: In function 'void init(std::vector<int>&, std::vector<std::pair<long long int, long long int> >&)':
nile.cpp:9:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i = 0; i < b.size(); ++i)
      |                  ~~^~~~~~~~~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:79:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   while (j < eve.size() && eve[j][0] <= y){
      |          ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 21408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 20164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 20164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 352 KB Time limit exceeded
2 Halted 0 ms 0 KB -