Submission #1198695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198695		tamyte	Nile (IOI24_nile)	C++20	100 / 100	86 ms	15680 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*

5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/
ll res = 0;
const int MAXN = 1e5;
ll pmn[MAXN + 1][2];
int l[MAXN];
ll mn[MAXN], sums[MAXN + 1];

ll update(int x);
struct DSU {
    vector<int> e;
    DSU(int n) {
        e = vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    int size(int x) {
        return -e[get(x)];
    }
    void unite(int x, int y) {
        x = get(x);
        y = get(y);
        // cout << "MERGING = " << x << " " << y << endl;
        if (x == y) return;
        res -= update(x);
        res -= update(y);
        l[x] = min(l[x], l[y]);
        sums[x] += sums[y];
        // cout << "BEFORE: x  | y\n";
        // for (int j = 0; j < 2; ++j) {
        	// cout << pmn[x][j] << " " << pmn[y][j] << endl;
        // }
        // cout << endl;
        for (int j = 0; j < 2; ++j) {
            pmn[x][j] = min(pmn[x][j], pmn[y][j]);
        }
        // cout << "AFTER: x  | y\n";
        // for (int j = 0; j < 2; ++j) {
        	// cout << pmn[x][j] << " " << pmn[y][j] << endl;
        // }
        // cout << endl;
        mn[x] = min(mn[x], mn[y]);
        e[x] += e[y];
        e[y] = x;
        res += update(x);
    }
} dsu(MAXN + 1);

ll update(int x) {
	assert(x == dsu.get(x));
    int p = l[x];
    return sums[x] + ((dsu.size(x) & 1) ? min(mn[x], pmn[x][p & 1]) : 0);
}







std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int Q = (int)E.size();
  int N = W.size();
  vector<array<int, 3>> data(N);
    for (int i = 0; i < N; ++i) {
    	data[i] = {W[i], A[i], B[i]};
    }
    sort(begin(data), end(data));
    for (int i = 0; i < N; ++i) {
    	ll now = data[i][2] - data[i][1];
    	pmn[i][0] = pmn[i][1] = LLONG_MAX;
    	pmn[i][i & 1] = -now;
    	sums[i] = now;
		l[i] = i;
		mn[i] = LLONG_MAX;
		res += data[i][1];
    }
    
//    for (int i = 0; i < N; ++i) {
//        cout << W[order[i]] << " ";
//
//    }
	vector<array<int, 3>> events;
    vector<ll> R(Q);
    for (int i = 0; i < Q; ++i) {
    	events.push_back({E[i], 2, i});
    }
    for (int i = 0; i < N - 1; ++i) {
    	events.push_back({data[i + 1][0] - data[i][0], 0, i});
    	if (i + 2 < N) {
    		events.push_back({data[i + 2][0] - data[i][0], 1, i});
    	}
    }
    // cout << res << endl;
    sort(begin(events), end(events));
    // for (auto& e : events) {
	    // int lst = 0;
	    // int cnt = 0;
	    // for (auto& u : e) {
	    	// cnt++;
    		// if (cnt == 3) cout << u << " ";
    		// if (cnt == 2)lst = u;
    	// }
    	// if (lst == 2) cout << " = query";
    	// else if (lst == 0) cout << " = (i, i + 1)";
    	// else cout << " = (i, i + 2)";
    	// cout << endl;
	// }
	// cout << endl;
    for (auto& e : events) {
    	
    	if (e[1] == 2) R[e[2]] = res;
    	else if (e[1] == 0) {
    		dsu.unite(e[2], e[2] + 1);
    	} else {
    		int x = dsu.get(e[2]);
    		res -= update(x);
    		int i = e[2] + 1;
    		ll nw = data[i][1] - data[i][2];
    		// cout << e[2] << " " << x << " = ";
    		// cout << mn[x] << " => ";
    		mn[x] = min(mn[x], nw);
    		// cout << mn[x] << endl;
    		res += update(x);
    	}
    	// cout << " -> " << res << endl;
    }
    return R;
}

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