Submission #1102203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102203		nhphuc	Nile (IOI24_nile)	C++17	38 / 100	71 ms	15000 KiB

nile

#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;
}

const int N = 100007;

vector<int> par(N), mn(N), sum(N), sz(N), val(N); 

int acs (int u){
	return (u == par[u] ? u : par[u] = acs(par[u]));
} 

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();
	vector<int> ans(q); vector<pair<int, int>> d(q), x(n), events;
	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 = 0;
	for (int i = 0; i < n; ++i){
		res += 1ll * a[i];
		par[i] = i;
		sz[i] = 1;
		sum[i] = b[i];
		mn[i] = a[i] - b[i];
		val[i] = a[i];
	}
	for (int i = 0; i < n - 1; ++i)
		events.push_back({w[i + 1] - w[i], i});
	sort(events.begin(), events.end());
	int j = 0;
	for (auto [x, y] : d){
		while (j < events.size() && events[j].first <= x){
			int i = events[j].second;
			int u = acs(i);
			int v = acs(i + 1);
			res -= val[u] + val[v];
			if (sz[u] < sz[v])
				swap(u, v);
			par[v] = u;
			sz[u] += sz[v];
			mn[u] = min(mn[u], mn[v]);
			sum[u] += sum[v];
			val[u] = (sz[u] % 2ll ? sum[u] + mn[u] : sum[u]);
			res += val[u];
			++j;
		}
		ans[y] = res;
	}
	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 (stderr)

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:51:12: 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]
   51 |   while (j < events.size() && events[j].first <= x){
      |          ~~^~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18