Submission #1136269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136269		naneosmic	Nile (IOI24_nile)	C++20	100 / 100	115 ms	24492 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define mp make_pair
using namespace std;
int n;
int curr=0;
struct node{
    int ans;
    int even;
    int evenskip;
    int odd;
    int oddskip;
    int size;
    void operator+(node a){
        curr-=this->ans;
        curr-=a.ans;
        if(this->size==1){
            this->even=min(this->even,a.odd);
            this->odd=min(this->odd,a.even);
            this->evenskip=min(this->evenskip,a.oddskip);
            this->oddskip=min(this->oddskip,a.evenskip);
        }else{
            this->even=min(this->even,a.even);
            this->odd=min(this->odd,a.odd);
            this->evenskip=min(this->evenskip,a.evenskip);
            this->oddskip=min(this->oddskip,a.oddskip);
        }
        this->size+=a.size;
        this->size%=2;
        if(this->size==0)ans=0;
        else{
            ans=min(this->odd,this->evenskip);
        }
        curr+=this->ans;
        return;
    }
};
struct dsu{
    vector<int>parent;
    vector<int>vals;
    vector<node>v;
    dsu(vector<pair<int,pair<int,int>>>&artifact){
        parent.resize(n);
        vals.resize(n);
        for(int i=0;i<n;i++)parent[i]=i;
        v.resize(n);
        for(int i=0;i<n;i++){
            curr+=artifact[i].second.second;
            int val=artifact[i].second.second-artifact[i].second.first;
            vals[i]=val;
            v[i].ans=val;
            v[i].odd=val;
            v[i].size=1;
            v[i].even=LLONG_MAX;
            v[i].evenskip=LLONG_MAX;
            v[i].oddskip=LLONG_MAX;
        }
    }
    int query(int a){
        if(parent[a]==a){
            return a;
        }
        return parent[a]=query(parent[a]);
    }
    void merge(int a,int b){
        int ff=query(a),ss=query(b);
        if(ff==ss)return;
        if(ff<ss){
            parent[ss]=ff;
            v[ff]+v[ss];
        }else{
            parent[ff]=ss;
            v[ss]+v[ff];
        }
    }
    void update(int idx){
        int par=query(idx);
        curr-=v[par].ans;
        int broj=idx-par+1;
        broj%=2;
        if(broj==0){
            v[par].evenskip=min(v[par].evenskip,vals[idx]);
        }else{
            v[par].oddskip=min(v[par].oddskip,vals[idx]);
        }
        v[par].ans=min(v[par].odd,v[par].evenskip);
        if(v[par].size==0LL)v[par].ans=0LL;
        curr+=v[par].ans;
    }
};
vector<int> calculate_costs(vector<signed> W, vector<signed> A,vector<signed> B, vector<signed> E) {
    n=A.size();
    vector<pair<int,pair<int,int>>>artifact(n);
    for(int i=0;i<n;i++){
        artifact[i].first=W[i];
        artifact[i].second.first=B[i];
        artifact[i].second.second=A[i];
    }
    sort(artifact.begin(),artifact.end());
    dsu solution(artifact);
    priority_queue<pair<int,pair<int,int>>>q;
    for(int i=0;i<n-1;i++){
        q.push(mp(-(artifact[i+1].first-artifact[i].first),mp(i,i+1)));
    }
    for(int i=0;i<n-2;i++){
        q.push(mp(-(artifact[i+2].first-artifact[i].first),mp(i,i+2)));
    }
    vector<pair<int,int>>nums;
    vector<int>answers;
    nums.push_back(mp(0LL,0LL));
    answers.push_back(curr);
    while(!q.empty()){
        pair<int,pair<int,int>>p=q.top();
        q.pop();
        p.first*=(-1);
        nums.push_back(mp(p.first,nums.size()));
        if(p.second.second-p.second.first==1){
            solution.merge(p.second.first,p.second.second);
        }else{
            solution.update(p.second.first+1);
        }
        answers.push_back(curr);
    }
    signed Q = (signed)E.size();
    vector<int> R(Q);
    for(int i=0;i<Q;i++){
        int c=E[i];
        auto it=upper_bound(nums.begin(),nums.end(),mp(c+1,-1LL));
        it--;
        pair<int,int>p=*it;
        R[i]=answers[p.second];
    }
    return R;
}

• 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