Submission #1250482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250482		caganyanmaz	Nile (IOI24_nile)	C++17	38 / 100	63 ms	8860 KiB

nile

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

• 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