Submission #1131915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131915		garam1732	Nile (IOI24_nile)	C++20	38 / 100	56 ms	11840 KiB

nile

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 2e18;

int par[MAXN];
ll sum[MAXN], mn[MAXN], cnt[MAXN];

int root(int x) { return par[x]==x?x:par[x]=root(par[x]); }
vector<pi> v, qry;
vector<ll> res;

struct Artifact {
    ll w,a,b;
}arr[MAXN];

ll f(int x) {
    ll t = sum[x];
    if(cnt[x]&1) t -= mn[x];
    return t;
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {

    int n = W.size();
    for(int i=0; i<n; i++) par[i] = i;

    for(int i=0; i<n; i++) arr[i] = {W[i], A[i], B[i]};
    sort(arr, arr+n, [&](Artifact &a, Artifact &b) { return a.w < b.w; });

    for(int i=1; i<n; i++) v.push_back(pi(abs(arr[i].w-arr[i-1].w), i));
    sort(all(v));

    int q=E.size();
    for(int i=0; i<q; i++) qry.push_back(pi(E[i], i));
    sort(all(qry));

    ll t = 0;
    for(int x:A) t+=x;
    for(int i=0; i<n; i++) sum[i] = mn[i] = arr[i].a-arr[i].b, cnt[i]=1;

    res.resize(q);
    for(int i=0, j=0; j<q; j++) {
        while(i<v.size() && v[i].ff <= qry[j].ff) {
            int x = root(v[i].ss-1);

            t += f(x); t += f(v[i].ss);
            sum[x] += sum[v[i].ss];
            mn[x] = min(mn[x], mn[v[i].ss]);
            cnt[x] += cnt[v[i].ss];
            par[v[i].ss] = x;
            t -= f(x);

            i++;
        }

        res[qry[j].ss] = t;
    }

    return res;
}

• 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