Submission #1231681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231681		Ghulam_Junaid	Nile (IOI24_nile)	C++20	100 / 100	80 ms	14272 KiB

nile

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

#define F first
#define S second

typedef long long ll;

const int N = 1e5 + 10;
int n, q, sz[N], mn[N][3], par[N];
ll res, sm[N], ans[N];
vector<int> w, a, b, e;
vector<ll> output;

int root(int v){
    return (par[v] == -1 ? v : par[v] = root(par[v]));
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return ;

    res -= ans[u], res -= ans[v];
    par[u] = v;
    sm[v] += sm[u];
    
    if (sz[v] % 2){
        mn[v][0] = min(mn[v][0], mn[u][1]);
        mn[v][1] = min(mn[v][1], mn[u][0]);
    }
    else{
        mn[v][0] = min(mn[v][0], mn[u][0]);
        mn[v][1] = min(mn[v][1], mn[u][1]);
    }
    mn[v][2] = min(mn[v][2], mn[u][2]);
    
    sz[v] += sz[u];
    ans[v] = sm[v] + min(mn[v][1], mn[v][2]) * (sz[v] % 2);
    res += ans[v];
}

void upd(int u){
    int v = root(u);
    mn[v][2] = min(mn[v][2], a[u] - b[u]);

    res -= ans[v];
    ans[v] = sm[v] + min(mn[v][1], mn[v][2]) * (sz[v] % 2);
    res += ans[v];
}

vector<ll> calculate_costs(vector<int> ww, vector<int> aa, vector<int> bb, vector<int> ee) {
    n = (int)ww.size(), q = (int)ee.size();
    w = ww, a = aa, b = bb, e = ee;
    output.resize(q, 0);

    vector<pair<int, pair<int, int>>> vec;
    for (int i = 0; i < n; i ++)
        vec.push_back({w[i], {a[i], b[i]}});
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i ++)
        w[i] = vec[i].F, a[i] = vec[i].S.F, b[i] = vec[i].S.S;

    vector<pair<int, int>> que;
    for (int i = 0; i < q; i ++)
        que.push_back({e[i], i});
    sort(que.begin(), que.end());

    vector<pair<int, int>> edges[2];
    for (int i = 1; i < n; i ++){
        edges[0].push_back({w[i] - w[i - 1], i});
        if (i + 1 < n)
            edges[1].push_back({w[i + 1] - w[i - 1], i});
    }
    for (int id : {0, 1}){
        sort(edges[id].begin(), edges[id].end());
        reverse(edges[id].begin(), edges[id].end());
    }

    for (int v = 0; v < n; v ++){
        sz[v] = 1, sm[v] = b[v], par[v] = -1;
        mn[v][0] = mn[v][2] = 1e9, mn[v][1] = a[v] - b[v];
        ans[v] = a[v];
        res += ans[v];
    }

    for (auto [d, id] : que){
        while (!edges[0].empty() and (edges[0].back()).F <= d){
            int i = (edges[0].back()).S;
            merge(i, i - 1);
            edges[0].pop_back();
        }
        while (!edges[1].empty() and (edges[1].back()).F <= d){
            int i = (edges[1].back()).S;
            upd(i);
            edges[1].pop_back();
        }
        output[id] = res;
    }
    return output;
}

• 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