Submission #1126517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126517		Muhammet	Nile (IOI24_nile)	C++20	100 / 100	757 ms	99964 KiB

nile

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

using namespace std;

#define ll long long
#define sz(s) (int)s.size()
#define ff first
#define ss second

ll sp[5][200005][30];

vector <vector <ll>> st;

ll f(int x, int y, bool z){
    int lg1 = log2(y-x+1);
    return min(sp[z][x][lg1],sp[z][y-(1LL<<lg1)+1][lg1]);
}

ll upd(int nd, int l, int r, int ind, bool z, ll vl){
    if(l > ind or r < ind) return st[z][nd];
    if(l == r) return st[z][nd] = vl;
    int md = (l + r) / 2;
    return st[z][nd] = min(upd(nd*2,l,md,ind,z,vl), upd(nd*2+1,md+1,r,ind,z,vl));
}

ll fnd(int nd, int l, int r, int x, int y, bool z){
    if(l > y or r < x) return 1e18;
    if(l >= x and r <= y) return st[z][nd];
    int md = (l + r) / 2;
    return min(fnd(nd*2,l,md,x,y,z), fnd(nd*2+1,md+1,r,x,y,z));
}

vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
    int q = sz(e), n = sz(a);
    vector <int> e1 = e;
    vector <ll> vans;
    sort(e.begin(), e.end());
    ll d = e[0];
    vector <pair<ll,pair<ll,ll>>> v;
    for(int i = 0; i < n; i++){
        v.push_back({w[i],{a[i],b[i]}});
    }
    map <pair<int,int>, ll> m;
    map <int,int> m1;
    sort(v.begin(), v.end());
    ll ans = 0;
    bool tr = 0;
    set <int> s;
    vector <pair<ll,int>> dis, dis1;
    for(int i = 0; i < n-1; i++){
        int ind = i;
        while(ind < (n-1)){
            if(v[ind+1].ff - v[ind].ff > d) break;
            ind++;
        }
        ll k = 0;
        for(int j = i; j <= ind; j++){
            k += (v[j].ss.ss);
        }
        ll k2 = k;
        k = 1e18;
        if((ind-i) % 2 == 1){
            k = k2;
        }
        else {
            for(int j = i; j <= ind; j++){
                ll k1 = k2;
                k1 -= (v[j].ss.ss);
                k1 += (v[j].ss.ff); 
                if((j-i) % 2 == 0){
                    k = min(k, k1);
                }
                else {
                    if(v[j+1].ff-v[j-1].ff <= d){
                        k = min(k, k1);
                    }
                }
            }
            k = min(k, k2 + (v[i].ss.ff-v[i].ss.ss));
            k = min(k, k2 + (v[ind].ss.ff-v[ind].ss.ss));
        }
        if(ind != n-1){
            dis.push_back({v[ind+1].ff-v[ind].ff,ind});
        }
        m[{i,ind}] = k;
        s.insert(ind);
        m1[i] = ind;
        m1[ind] = i;
        i = ind;
        ans += k;
        if(i == n-1) tr = 1;
    }
    if(tr == 0){
        ans += v[n-1].ss.ff;
        m[{n-1,n-1}] = v[n-1].ss.ff;
        m1[n-1] = n-1;
        s.insert(n-1);
    }
    sort(dis.rbegin(), dis.rend());
    vector <ll> v1, p(n,0);
    p[0] = v[0].ss.ss;
    for(int i = 1; i < n; i++){
        p[i] = p[i-1] + v[i].ss.ss;
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
            for(int i1 = 0; i1 < 27; i1++){
                sp[i][j][i1] = 1e18;
            }
        }
    }
    for(int i = 0; i < n; i++){
        sp[i%2][i][0] = (v[i].ss.ff-v[i].ss.ss);
    }
    for(int j = 1; j < 27; j++){
        for(int i = 0; i < n-(1LL<<j)+1; i++){
            sp[0][i][j] = min(sp[0][i][j-1],sp[0][i+(1LL<<(j-1))][j-1]);
            sp[1][i][j] = min(sp[1][i][j-1],sp[1][i+(1LL<<(j-1))][j-1]);
        }
    }
    for(int i = 1; i < n-1; i++){
        dis1.push_back({(v[i+1].ff-v[i-1].ff),i});
    }
    sort(dis1.rbegin(), dis1.rend());
    st.assign(3, vector <ll> (n*8,1e18));
    map <ll,ll> mp;
    mp[d] = ans;
    for(int i = 1; i < q; i++){
        d = e[i];
        while(sz(dis1) > 0){
            if(d >= dis1.back().ff){
                int x = dis1.back().ss;
                dis1.pop_back();
                upd(1,0,n-1,x,x%2,(v[x].ss.ff-v[x].ss.ss));
                int y = *s.lower_bound(x);
                int y1 = m1[y];
                ll z1 = ((y1 != y and (y-y1+1) % 2 == 1) ? fnd(1,0,n-1,y1+1,y-1,1-(y1%2)) : 1e18), z2 = p[y];
                if(y1 != 0) z2 -= p[y1-1];
                if(z1+z2 < m[{y1,y}]){
                    ans -= m[{y1,y}];
                    ans += (z1+z2);
                    m[{y1,y}] = (z1+z2);
                }
            }
            else break;
        }
        while(sz(dis) > 0){
            if(d >= dis.back().ff){
                int x = dis.back().ss;
                dis.pop_back();
                s.erase(s.find(x));
                ans -= m[{m1[x],x}];
                ans -= m[{x+1,m1[x+1]}];
                int a1 = m1[x], b1 = m1[x+1];
                m1[a1] = b1;
                m1[b1] = a1;
                ll y = p[b1];
                if(a1 > 0) y -= p[a1-1];
                if((b1-a1) % 2 == 1){
                    m[{a1,b1}] = y;
                }
                else {
                    ll a2 = (f(a1,b1,(a1%2)));
                    if(a1 != b1) a2 = min(a2,fnd(1,0,n-1,a1+1,b1-1,1-(a1%2)));
                    y += a2;
                    m[{a1,b1}] = y;
                }
                ans += y;
            }
            else break;
        }
        mp[d] = ans;
    }
    for(auto i : e1){
        vans.push_back(mp[i]);
    }
    return vans;
}

• 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