Submission #1141071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141071		Luvidi	Nile (IOI24_nile)	C++20	32 / 100	57 ms	12104 KiB

nile

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

long long sum;

struct Seg{
    Seg *par;
    long long sz,val;
    Seg(long long x){
        sz=1;
        par=this;
        val=x;
    }
    Seg *rep(){
        if(par==this)return this;
        return par=par->rep();
    }
    void join(Seg *seg2){
        if(sz%2)sum-=val;
        if(seg2->sz%2)sum-=seg2->val;
        seg2->par=this;
        sz+=seg2->sz;
        if(sz%2)sum+=val;
    }
};

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();
    pair<int,pair<long long,long long>> a[n];
    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);
        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());
        }
        ans[idx]=sum;
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18