제출 #1250482

#제출 시각아이디문제언어결과실행 시간메모리
1250482caganyanmazNile (IOI24_nile)C++17
38 / 100
63 ms8860 KiB
#include <bits/stdc++.h> #include "nile.h" using namespace std; vector<array<int, 2>> get_sorted_indices(const vector<int>& v); void sort_stuff(vector<int>& w, vector<int>& a, vector<int>& b); long long calculate_expense(const vector<int>& c, int size, int le, int skip); void swap(int& l, int& r); int ind_min(const vector<int>& c, int a, int b); long long merge(vector<int>& head, vector<int>& nxt, vector<int>& tail, vector<int>& size, vector<int>& lo, vector<int>& le, vector<int>& skip, const vector<int>& c, int l, int r); long long update_skip(const vector<int>& c, const vector<int>& head, const vector<int>& size, const vector<int>& le, vector<int>& skip, int i); vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) { sort_stuff(w, a, b); int n = w.size(); int q = e.size(); // for (int i = 0; i < n; i++) cout << w[i] << " "; cout << "\n"; // for (int i = 0; i < n; i++) cout << a[i] << " "; cout << "\n"; // for (int i = 0; i < n; i++) cout << b[i] << " "; cout << "\n"; // for (int i = 0; i < q; i++) cout << e[i] << " " ; cout << "\n"; vector<array<int, 2>> ei = get_sorted_indices(e); vector<array<int, 2>> intervals(n-1); for (int i = 0; i < n - 1; i++) { intervals[i] = {w[i+1] - w[i], i}; } sort(intervals.begin(), intervals.end()); vector<int> c(n); for (int i = 0; i < n; i++) c[i] = a[i] - b[i]; vector<int> head(n), nxt(n), tail(n), size(n), lo(n), le(n), skip(n); for (int i = 0; i < n; i++) { head[i] = i; nxt[i] = -1; tail[i] = i; size[i] = 1; lo[i] = -1; le[i] = i; skip[i] = -1; } long long cost = 0; for (int i = 0; i < n; i++) cost += a[i]; int cnt = 0; vector<long long> res(q); for (auto [d, idx] : ei) { // Merge shit // cout << cost << " " << d << "\n"; while (cnt < n-1 && intervals[cnt][0] <= d) { int i = intervals[cnt][1]; cost += merge(head, nxt, tail, size, lo, le, skip, c, head[i], head[i + 1]); if (i > 0 && w[i+1] - w[i-1] <= d) { cost += update_skip(c, head, size, le, skip, i); } if ((i+2) < n && w[i+2] - w[i] <= d) { cost += update_skip(c, head, size, le, skip, i+1); } cnt++; } // cout << idx << " " << cost << "\n"; res[idx] = cost; } return res; } long long merge(vector<int>& head, vector<int>& nxt, vector<int>& tail, vector<int>& size, vector<int>& lo, vector<int>& le, vector<int>& skip, const vector<int>& c, int l, int r) { long long change = - calculate_expense(c, size[l], le[l], skip[l]) - calculate_expense(c, size[r], le[r], skip[r]); int new_lo, new_le, new_size, new_skip; // Cost shit if ((size[l] % 2) == 0) { new_lo = ind_min(c, lo[l], lo[r]); new_le = ind_min(c, le[l], le[r]); } else { // cout << "LO: " << lo[l] << "LE: " << le[r] << "\n"; new_lo = ind_min(c, lo[l], le[r]); new_le = ind_min(c, le[l], lo[r]); } new_size = size[l] + size[r]; new_skip = ind_min(c, skip[l], skip[r]); change += calculate_expense(c, new_size, new_le, new_skip); // cout << change << " " << l << " " << r << "\n"; // cout << "Size: " << new_size << " Skip: " << new_skip << " le: " << new_le << " lo: "<< new_lo << "\n"; if (size[r] > size[l]) swap(l, r); nxt[tail[l]] = r; tail[l] = tail[r]; while (r != -1) { head[r] = l; r = nxt[r]; } size[l] = new_size; skip[l] = new_skip; lo[l] = new_lo; le[l] = new_le; return change; } long long update_skip(const vector<int>& c, const vector<int>& head, const vector<int>& size, const vector<int>& le, vector<int>& skip, int i) { long long change = -calculate_expense(c, size[head[i]], le[head[i]], skip[head[i]]); skip[head[i]] = ind_min(c, skip[head[i]], i); change += calculate_expense(c, size[head[i]], le[head[i]], skip[head[i]]); // cout << "Skip updated: " << i << " " << change << "\n"; return change; } long long calculate_expense(const vector<int>& c, int size, int le, int skip) { if (size % 2 == 0) return 0; return c[ind_min(c, le, skip)]; } void swap(int& l, int& r) { int tmp = l; l = r; r = tmp; } int ind_min(const vector<int>& c, int a, int b) { if (a == -1) return b; if (b == -1) return a; if (c[a] < c[b]) return a; return b; } vector<array<int, 2>> get_sorted_indices(const vector<int>& v) { vector<array<int, 2>> res(v.size()); for (int i = 0; i < v.size(); i++) res[i] = {v[i], i}; sort(res.begin(), res.end()); return res; } void sort_stuff(vector<int>& w, vector<int>& a, vector<int>& b) { const int n = w.size(); vector<array<int, 2>> wi = get_sorted_indices(w); vector<int> wr(n), ar(n), br(n); for (int i = 0; i < n; i++) { ar[i] = a[wi[i][1]]; br[i] = b[wi[i][1]]; wr[i] = w[wi[i][1]]; } a = ar; b = br; w = wr; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...