Submission #1207674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207674		vidux	Nile (IOI24_nile)	C++17	0 / 100	25 ms	5516 KiB

nile

#include <bits/stdc++.h>
using namespace std;

//#define LOCAL

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int INF = 1e9;
const ll LLINF = 1e18;

struct DSU {
	vi sz, par;
	DSU(int n) {
		sz = vi(n, 1);
		par = vi(n);
		FOR(i, n) par[i] = i;
	}
	int find(int x) {
		return par[x] = ((par[x] == x) ? x : find(par[x]));
	}
	bool join(int x, int y) {
		if (find(x) == find(y)) return false;
		if (sz[find(y)] > sz[find(x)]) swap(x, y); 
		sz[find(x)] += sz[find(y)];
		par[find(y)] = find(x);
		return true;
	}
};

vl calculate_costs(vi W, vi A, vi B, vi E) {
	int n = SZ(W);
	int q = SZ(E);
	vector<pii> Q(q);
	FOR(i, q) Q[i] = {E[i], i};
	sort(ALL(Q));
	vector<pair<int, pii>> arr(n);
	FOR(i, n) arr[i] = {W[i], {A[i], B[i]}};
	vector<pii> D(n-1);
	FOR(i, n-1) D[i] = {abs(arr[i].first-arr[i+1].first), i}; 
	sort(RALL(D));
	int d = 0;
	ll cur = 2*n;
	vl ans(q);
	DSU dsu(n);
	FOR(t, q) {
		d = Q[t].fi;
		while (SZ(D) && D.back().fi <= d) {
			int sz1 = dsu.sz[dsu.find(D.back().se)]; 
			int sz2 = dsu.sz[dsu.find(D.back().se+1)];
			cur -= (sz1/2)*2+(sz1%2)*2 + (sz2/2)*2+(sz2%2)*2;
			dsu.join(D.back().se, D.back().se+1);
			sz1 = dsu.sz[dsu.find(D.back().se)]; 
			cur += (sz1/2)*2+(sz1%2)*2;
			D.pop_back();
		}
		ans[Q[t].se] = cur;
	}
	return ans;
}

#ifdef LOCAL
int main() {
	vl ans = calculate_costs(
		{1, 2, 4, 5, 8, 10, 12},
		{2, 2, 2, 2, 2, 2, 2},
		{1, 1, 1, 1, 1, 1, 1},
		{5, 2, 1}
	);
	FORR(x, ans) cout << x << endl;
    return 0;
}
#endif

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