Submission #1209259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209259		andrej246	Nile (IOI24_nile)	C++20	100 / 100	282 ms	38252 KiB

nile

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

#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i < (n); i++)
#define PRINTV(v) for (auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vvl trees(2);
ll update(vl& tree, ll k, ll x, ll l, ll r, ll i) {
    if (k < l || r <= k) return tree[i];
    if (l+1 >= r) return tree[i] = x;
    ll m = (l+r)/2;
    return tree[i] = min(update(tree,k,x,l,m,2*i+1),update(tree,k,x,m,r,2*i+2));
}

ll query(vl& tree, ll ql, ll qr, ll l, ll r, ll i) {
    if (ql <= l && r <= qr) return tree[i];
    if (r <= ql || qr <= l) return 1e18;
    ll m = (l+r)/2;
    return min(query(tree,ql,qr,l,m,2*i+1),query(tree,ql,qr,m,r,2*i+2));
}

vl dsu;
vl l;
vl r;
ll n;

ll find(ll u) {
    if (dsu[u] == u) return u;
    else return dsu[u] = find(dsu[u]);
}

void unite(ll x, ll y) {
    ll a = find(x);
    ll b = find(y);
    dsu[b] = a;
    l[a] = min(l[a],l[b]);
    r[a] = max(r[a],r[b]);
}

ll get_ans(ll x) {
    ll a = find(x);
    if ((l[a] % 2) != (r[a] % 2)) return 0;
    return query(trees[l[a]%2],l[a],r[a]+1,0,n,0);
}

std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> e) {

    int q = (ll)e.size();

    n = w.size();

    vpl tosort;
    FOR(i,n) tosort.push_back({w[i],i});
    sort(all(tosort));
    vl x(n);
    FOR(i,n) x[i] = tosort[i].f;

    vl c(n);
    ll bsum = 0;
    ll cur = 0;
    FOR(i,n) {
        bsum += b[i];
        ll j = tosort[i].s;
        c[i] = a[j]-b[j];
        cur += c[i];
    }

    trees[0].resize(4*n);
    trees[1].resize(4*n);
    FOR(i,n) {
        update(trees[i%2],i,c[i],0,n,0);
        update(trees[(i+1)%2],i,1e18,0,n,0);
    }

    set<ll> stuffhappens;
    map<ll,vl> skips;
    map<ll,vpl> joins;
    map<ll,ll> queries;
    for (auto k: e) queries[k] = 0;

    FOR(i,n-1) {
        joins[abs(x[i+1]-x[i])].push_back({i,i+1});
    }
    FORS(i,1,n-1) {
        skips[abs(x[i+1]-x[i-1])].push_back(i);
    }

    dsu.resize(n);
    l.resize(n);
    r.resize(n);
    FOR(i,n) dsu[i] = l[i] = r[i] = i;

    for (auto [k,s]: skips) stuffhappens.insert(k);
    for (auto [k,s]: joins) stuffhappens.insert(k);
    for (auto [k,s]: queries) stuffhappens.insert(k);

    for (auto d: stuffhappens) {
        for (auto [a,b]: joins[d]) {
            cur -= get_ans(a);
            cur -= get_ans(b);
            unite(a,b);
            cur += get_ans(a);
        }
        for (auto i: skips[d]) {
            cur -= get_ans(i);
            update(trees[(i+1)%2],i,c[i],0,n,0);
            cur += get_ans(i);
        }
        if (queries.count(d) > 0) {
            queries[d] = cur;
        }
    }

    vl ans(q);
    FOR(i,q) ans[i] = queries[e[i]]+bsum;
    return ans;
}

• 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