Submission #1258653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258653		nerrrmin	Nile (IOI24_nile)	C++20	100 / 100	115 ms	25784 KiB

nile

#include "nile.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 3e5 + 10;
long long n, q;
long long w[maxn], a[maxn], b[maxn];

long long dp[maxn]; /// best match count
long long r[maxn];
long long ans;
long long pa[maxn], sz[maxn], res[maxn], gl[maxn], gr[maxn];
long long best_odd[maxn], best_even[maxn], bs[maxn];
long long other[maxn];

long long t[maxn * 4], val[maxn];

void build_tree(long long i, long long l, long long r)
{
    if(l == r)
    {
        t[i] = 1e17;
        return;
    }
    long long mid = (l + r)/2;
    build_tree(2*i, l, mid);
    build_tree(2*i+1, mid+1, r);
    t[i] = 1e17;
}

long long ql, qr;
long long query(long long i, long long l, long long r)
{
    if(qr < ql)return 1e17;
    if(qr < l || ql > r)return 1e17;
    if(ql <= l && r <= qr)return t[i];
    long long mid = (l + r)/2;
    return min(query(2*i, l, mid), query(2*i+1, mid+1, r));
}

long long upos;
void update(long long i, long long l, long long r)
{
    if(l == r)
    {
       // cout << "updated " << val[l] << endl;
        t[i] = val[l];
        return;
    }
    long long mid = (l + r)/2;
    if(upos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = min(t[2*i], t[2*i+1]);

}
long long find_leader(long long i)
{
    if(pa[i] == i)return i;
    return (pa[i] = find_leader(pa[i]));
}
void change(int i, int index)
{long long nowans = res[i];
ans -= nowans;
    if(index > gl[i] && index < gr[i])
    {
        other[i] = min(other[i], val[index]);
        res[i] = bs[i];
        long long cut = min(best_odd[i],  other[i]);
        if(sz[i] & 1)res[i] += cut;
    }
    ans += res[i];
}
void unite(long long i, long long j)
{
    i = find_leader(i);
    j = find_leader(j);
    if(i == j)return;
    if(i > j)swap(i, j);

    ans -= res[i];
    ans -= res[j];
    long long lft = sz[i];
    sz[i] += sz[j];
    pa[j] = i;
    gl[i] = min(gl[i], gl[j]);
    gr[i] = max(gr[i], gr[j]);


   // cout << gl[i] << ' ' << gr[i] << endl;
    if(lft & 1)
    {
        best_even[i] = min(best_even[i], best_odd[j]);
        best_odd[i] = min(best_odd[i], best_even[j]);
    }
    else
    {
        best_even[i] = min(best_even[i], best_even[j]);
        best_odd[i] = min(best_odd[i], best_odd[j]);
    }
    bs[i] += bs[j];
    res[i] = bs[i];
    long long cut = best_odd[i];
    ql = gl[i] + 1;
    qr = gr[i] - 1;
    long long newcut = query(1, 0, n-1);
    other[i] = newcut;
    cut = min(cut, newcut);
    if(sz[i] & 1)res[i] += cut;//(sz[i] % 2);

    ans += res[i];

}
vector < pair < long long, long long > > u;
void solve()
{
   vector < pair < long long, long long > > g;
   vector < pair < long long, long long > > v;
   for (long long i = 1; i < n; ++ i)
   {
       long long d = w[i] - w[i-1];
       g.push_back(make_pair(d, i-1));
   }
   for (long long i = 1; i < n-1; ++ i)
   {
       long long con = w[i+1] - w[i-1];
       v.pb(make_pair(con, i));
   }
   sort(g.begin(), g.end());
   sort(v.begin(), v.end());
   long long i = 0, j = 0;
    for (auto &[dif, pos]: u)
    {
        while(j < v.size() && v[j].first <= dif)
        {
            upos = v[j].second;
            update(1, 0, n-1);
            int lead = find_leader(upos);
            change(lead, upos);
            j ++;
        }
        while(i < g.size() && g[i].first <= dif)
        {
            long long posx = g[i].second;
            long long posy = posx + 1;
            unite(posx, posy);
            i ++;
        }
        r[pos] = ans;
    }
}

struct p
{
    long long w, a, b;
    p() {};
    p(long long _w, long long _a, long long _b)
    {
        w = _w;
        a = _a;
        b = _b;
    }
};

bool cmp(p p1, p p2)
{
    return (p1.w < p2.w);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E)
{
    n = W.size();
    for (long long i = 0; i < n; ++ i)
        w[i] = W[i];
    for (long long i = 0; i < n; ++ i)
        a[i] = A[i];
    for (long long i = 0; i < n; ++ i)
        b[i] = B[i];
    vector < p > g;
    for (long long i = 0; i < n; ++ i)
        g.pb(p(w[i], a[i], b[i]));
    sort(g.begin(), g.end(), cmp);
    long long i = 0;
    for (auto &[ww, aa, bb]: g)
    {

        w[i] = ww;
        a[i] = aa;
        b[i] = bb;
        i ++;
    }
    build_tree(1, 0, n-1);
    for (long long i = 0; i < n; ++ i)
    {
        val[i] = a[i] - b[i];
        pa[i] = i;
        sz[i] = 1;
        res[i] = a[i];
        bs[i] = b[i];
        other[i] = 1e17;
        best_odd[i] = a[i] - b[i];
        best_even[i] = 1e17;
        gl[i] = i;
        gr[i] = i;
        ans += a[i];
    }
    q = (long long)E.size();
    vector < long long > result;
    for (long long i = 0; i < E.size(); ++ i)
    {
        u.pb(make_pair(E[i], i));
    }
    sort(u.begin(), u.end());
    solve();

    for (long long i = 0; i < q; ++ i)
        result.pb(r[i]);
    return result;
}

• 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