제출 #1183023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183023		12345678	Nile (IOI24_nile)	C++20	100 / 100	244 ms	41016 KiB

nile

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

using namespace std;

#define ll long long

const ll nx=1e5+5, inf=1e18;

struct info
{
    ll w, a, b;
    info(ll w=0, ll a=0, ll b=0): w(w), a(a), b(b){}
    bool operator< (const info &o) const {return w<o.w;}
} d[nx];

struct segtree
{
    struct mat 
    {
        ll a[3][3];
        mat(int idx=-1)
        {
            for (int i=0; i<3; i++) for (int j=0; j<3; j++) a[i][j]=inf;
            if (idx!=-1)
            {
                a[0][0]=a[1][2]=d[idx].a;
                a[0][1]=d[idx].b;
            }
        }
    } node[4*nx];
    mat merge(mat &lhs, mat &rhs)
    {
        mat res;
        for (int i=0; i<3; i++) for (int j=0; j<3; j++) for (int k=0; k<3; k++) res.a[i][j]=min(res.a[i][j], lhs.a[i][k]+rhs.a[k][j]);
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return node[i]=mat(l), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        node[i]=merge(node[2*i], node[2*i+1]);
        //cout<<"after "<<l<<' '<<r<<' '<<node[i].a[0][0]<<'\n';
    }
    void update(int l, int r, int i, int idx, int t)
    {
        if (idx<l||r<idx) return;
        if (l==r)
        {
            //cout<<"update "<<idx<<' '<<t<<'\n';
            if (t==1) node[i].a[1][0]=d[l].b;
            else node[i].a[2][0]=d[l].b;
            return;
        }
        int md=(l+r)/2;
        update(l, md, 2*i, idx, t);
        update(md+1, r, 2*i+1, idx, t);
        node[i]=merge(node[2*i], node[2*i+1]);
    }
} s;

ll n, dp[nx];
vector<ll> res;
vector<pair<ll, ll>> qrs;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq1, pq2;

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 (int i=1; i<=n; i++) d[i]=info(W[i-1], A[i-1], B[i-1]);
    sort(d+1, d+n+1);
    for (int i=2; i<=n; i++) pq1.push({d[i].w-d[i-1].w, i});
    for (int i=3; i<=n; i++) pq2.push({d[i].w-d[i-2].w, i});
    res.resize(E.size());
    for (int i=0; i<E.size(); i++) qrs.push_back({E[i], i});
    sort(qrs.begin(), qrs.end());
    s.build(1, n, 1);
    //cout<<"debug "<<s.node[1].a[0][0]<<'\n';
    for (auto [x, idx]:qrs)
    {
        while (!pq1.empty()&&pq1.top().first<=x) s.update(1, n, 1, pq1.top().second, 1), pq1.pop();
        while (!pq2.empty()&&pq2.top().first<=x) s.update(1, n, 1, pq2.top().second, 2), pq2.pop();
        //cout<<"answer "<<idx<<'\n';
        res[idx]=s.node[1].a[0][0];
    }
    return res;
}

• 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