제출 #1141124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141124		Luvidi	나일강 (IOI24_nile)	C++20	100 / 100	87 ms	16320 KiB

nile

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

const int maxn=1e5;
pair<int,pair<long long,long long>> a[maxn];
long long sum;
priority_queue<pair<int,int>> pq;

struct Seg{
    Seg *par;
    int sz,l;
    long long val[2][2];
    Seg(long long x,int idx){
        sz=1;
        par=this;
        val[0][0]=x;
        val[0][1]=1e18;
        val[1][0]=1e18;
        val[1][1]=1e18;
        l=idx;
    }
    Seg *rep(){
        if(par==this)return this;
        return par=par->rep();
    }
    void join(Seg *seg2){
        if(sz%2)sum-=min(val[0][0],val[1][1]);
        if(seg2->sz%2)sum-=min(seg2->val[0][0],seg2->val[1][1]);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                val[i][j]=min(val[i][j],seg2->val[i^(sz&1)][j]);
            }
        }
        if(sz>1)pq.push({a[seg2->l-2].first-a[seg2->l].first,seg2->l-1});
        if(seg2->sz>1)pq.push({a[seg2->l-1].first-a[seg2->l+1].first,seg2->l});
        seg2->par=this;
        sz+=seg2->sz;
        if(sz%2)sum+=min(val[0][0],val[1][1]);
    }
};

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
                                        
    int n=W.size(),q=E.size();
    for(int i=0;i<n;i++)a[i]={W[i],{A[i],B[i]}};
    sort(a,a+n);
    pair<int,int> qry[q],ds[n-1];
    for(int i=0;i<q;i++)qry[i]={E[i],i};
    sort(qry,qry+q);
    for(int i=0;i<n-1;i++)ds[i]={a[i+1].first-a[i].first,i};
    sort(ds,ds+n-1);
    vector<long long> ans(q);
    Seg *seg[n];
    for(int i=0;i<n;i++){
        seg[i]=new Seg(a[i].second.first-a[i].second.second,i);
        sum+=a[i].second.first;
    }
    int ni=0;
    for(auto[d,idx]:qry){
        while(ni<n-1&&ds[ni].first<=d){
            int x=ds[ni++].second;
            seg[x]->rep()->join(seg[x+1]->rep());
        }
        while(!pq.empty()&&-pq.top().first<=d){
            int x=pq.top().second;
            pq.pop();
            auto s=seg[x]->rep();
            if(s->sz%2)sum-=min(s->val[0][0],s->val[1][1]);
            s->val[(s->l+x)%2][1]=min(s->val[(s->l+x)%2][1],a[x].second.first-a[x].second.second);
            if(s->sz%2)sum+=min(s->val[0][0],s->val[1][1]);
        }
        ans[idx]=sum;
    }
    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