Submission #1157566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157566		guanex	Nile (IOI24_nile)	C++20	0 / 100	49 ms	21688 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> pii;
#define vi vector<ll>
#define vii vector<ii>
#define vpii vector<pii>
#define whole(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back

ll fat[100005], sz[100005], le[100005], ri[100005];

const ll inf = 1000000000000000000;

struct segtree{
    ll n;
    vi t;
    segtree(vi &x){
        n = (ll)x.size();
        t.assign(4 * n + 5, inf);
        build(0, n-1, 1, x);
    }
    void build(ll l, ll r, ll no, vi &x){
        //cout << l << " " << r << endl;
        if(l == r){
            t[no] = x[l];
            return;
        }
        ll mid = l + (r - l) / 2;
        build(l, mid, 2*no, x);
        build(mid+1, r, 2*no+1, x);
        t[no] = min(t[2*no], t[2*no+1]);
        return;
    }
    void update(ll l, ll r, ll no, ll i, ll val){
        if(l == r){
            t[no] = val;
            return;
        }
        ll mid = l + (r - l) / 2;
        if(i <= mid){
            update(l, mid, 2*no, i, val);
        }else{
            update(mid+1, r, 2*no+1, i, val);
        }
        t[no] = min(t[2*no], t[2*no+1]);
    }
    ll query(ll l, ll r, ll no, ll lq, ll rq){
        if(l == lq && r == rq){
            return t[no];
        }
        ll mid = l + (r - l) / 2;
        if(lq > mid){
            return query(mid+1, r, 2*no+1, lq, rq);
        }else if(rq <= mid){
            return query(l, mid, 2*no, lq, rq);
        }
        ll lef = query(l, mid, 2*no, lq, mid);
        ll rig = query(mid+1, r, 2*no+1, mid+1, rq);
        return min(lef, rig);
    }
};

ll ffather(ll no){
    if(fat[no] == no){
        return no;
    }
    return fat[no] = ffather(fat[no]);
}

void join(ll u, ll v){
    u = ffather(u);
    v = ffather(v);
    if(u == v){
        return;
    }
    if(sz[u] < sz[v]){
        swap(u, v);
    }
    fat[v] = u;
    sz[u] += sz[v];
    le[u] = min(le[u], le[v]);
    ri[u] = max(ri[u], ri[v]);
}


std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> E) {
    for(ll i = 0; i < 100005; ++i){
        fat[i] = i;
        sz[i] = 1;
        le[i] = i;
        ri[i] = i;
    }
    ll n = ll(a.size());
    vpii x;
    ll sum = 0;
    for(ll i = 0; i < ll(w.size()); ++i){
        sum += a[i];
        x.pb({1LL * w[i], {1LL * a[i], 1LL * b[i]}});
    }
    vi even;
    vi odd;
    sort(whole(x));
    vii op;
    vii sop;
    even.pb(x[0].se.fi - x[0].se.se);
    odd.pb(inf);
    for(ll i = 1; i < (ll)x.size(); ++i){
        if(i % 2 == 0){
            even.pb(x[i].se.fi - x[i].se.se);
            odd.pb(inf);
        }else{
            odd.pb(x[i].se.fi - x[i].se.se);
            even.pb(inf);
        }
        if(i == (ll)x.size()-1){
            op.pb({x[i].fi - x[i-1].fi, i});
            continue;
        }
        op.pb({x[i].fi - x[i-1].fi, i});
        sop.pb({x[i+1].fi - x[i-1].fi, i});
    }
    segtree oddtree(odd), eventree(even);
    sort(whole(op));
    sort(whole(sop));
    vii q;
    for(ll i = 0; i < (ll)E.size(); ++i){
       q.pb({E[i], i});
    }
    sort(whole(q));
    std::vector<long long> ans((ll)q.size(), 0);
    ll i = 0;
    ll j = 0;
    for(auto e:q){
        ll val = e.fi;
        //cout << val << " ." << endl;
        unordered_set<ll> tocheck;
        while(i < (ll)op.size() && op[i].fi < val){
            ll v = op[i].se;
            ll u = v-1;
            v = ffather(v);
            u = ffather(u);
            if(u == v){
                i++;
                continue;
            }
            if(sz[v] % 2 == 1 && tocheck.find(v) == tocheck.end()){
                if(le[v] % 2 == 0){
                    sum -= eventree.query(0, n-1, 1, le[v], ri[v]);
                }else{
                    sum -= oddtree.query(0, n-1, 1, le[v], ri[v]);
                }
            }
            //cout << u << " " << v << " " << sum << endl;
            if(sz[u] % 2 == 1 && tocheck.find(u) == tocheck.end()){
                if(le[u] % 2 == 0){
                    sum -= eventree.query(0, n-1, 1, le[u], ri[u]);
                }else{
                    sum -= oddtree.query(0, n-1, 1, le[u], ri[u]);
                }
            }
            //cout << u << " " << v << " " << sum << endl;
            join(u, v);
            tocheck.insert(ffather(u));
            i++;
        }
        while(j < (ll)sop.size() && sop[j].fi <= val){
            ll u = sop[j].se;
            //cout << u << endl;
            if(u % 2 == 0){
                oddtree.update(0, n-1, 1, u, x[u].se.fi - x[u].se.se);
            }else{
                eventree.update(0, n-1, 1, u, a[u] - b[u]);
            }
            j++;
        }
        //cout << oddtree.query(0, n-1, 1, 0, 4) << endl;
        for(auto e:tocheck){
            if(sz[e] % 2 == 1){
                if(le[e] % 2 == 0){
                    sum += eventree.query(0, n-1, 1, le[e], ri[e]);
                }else{
                    sum += oddtree.query(0, n-1, 1, le[e], ri[e]);
                }
            }
        }
        ans[e.se] = sum;
    }
    return ans;
}

• 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