제출 #1149072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149072		Rares	나일강 (IOI24_nile)	C++20	38 / 100	67 ms	11712 KiB

nile

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

const int MAXN=1e5+10;
typedef long long ll;

struct query{
    int x,i;
}q[MAXN];
bool cmp3 (query a, query b){
    return a.x<b.x;
}

struct artefact{
    int w,c1,c2;
}a[MAXN];
bool cmp (artefact x, artefact y){
    return x.w<y.w;
}

struct dif{
    int x,l,r;
}d[MAXN];
bool cmp2 (dif a, dif b){
    return a.x<b.x;
}


int n,m,tata[MAXN],s[MAXN];
ll ans[MAXN],rez,sumc2[MAXN],dmin[MAXN],sum[MAXN];

int radacina (int x){
    if (tata[x]==x) return x;
    return tata[x]=radacina (tata[x]);
}
void unire (int x, int y){
    x=radacina (x),y=radacina (y);


    if (s[x]<s[y]) swap (x,y);
    rez-=sum[x];
    rez-=sum[y];

    s[x]+=s[y];
    tata[y]=x;
    sumc2[x]+=sumc2[y];
    dmin[x]=min (dmin[x],dmin[y]);
    if (s[x]%2==0) sum[x]=sumc2[x];
    else sum[x]=sumc2[x]+dmin[x];

    rez+=sum[x];
}

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 ();
    m=E.size ();
    for (int i=0;i<n;++i){
        a[i+1].w=W[i];
        a[i+1].c1=A[i];
        a[i+1].c2=B[i];

    }
    for (int i=0;i<m;++i){
        q[i+1]={E[i],i+1};
    }

    sort (a+1,a+n+1,cmp);

    for (int i=1;i<n;++i){
        d[i].x=a[i+1].w-a[i].w;
        d[i].l=i;
        d[i].r=i+1;
    }
    sort (d+1,d+n,cmp2);

    sort (q+1,q+m+1,cmp3);

    for (int i=1;i<=n;++i){
        s[i]=1;
        tata[i]=i;
        rez+=a[i].c1;
        sum[i]=a[i].c1;
        sumc2[i]=a[i].c2;
        dmin[i]=a[i].c1-a[i].c2;
    }

    int j=1;
    for (int i=1;i<=m;++i){
        while (j<=n-1 and q[i].x>=d[j].x){
            unire (d[j].l,d[j].r);

            j++;
        }
        ans[q[i].i]=rez;
    }

    vector <ll> aux;
    for (int i=1;i<=m;++i){
        aux.push_back (ans[i]);
    }
    return aux;
}

/*signed main()
{
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);
    vector <int> A,W,B,E;
    int n,q;
    cin >>n>>q;
    for (int i=1;i<=n;++i){
        int x;
        cin >>x;
        W.push_back (x);
    }
    for (int i=1;i<=n;++i){
        int x;
        cin >>x;
        A.push_back (x);
    }
    for (int i=1;i<=n;++i){
        int x;
        cin >>x;
        B.push_back (x);
    }
    for (int i=1;i<=q;++i){
        int x;
        cin >>x;
        E.push_back (x);
    }
    vector <ll> aux=calculate_costs (W,A,B,E);

    for (auto x:aux){
        cout <<x<<' ';
    }
    return 0;
}*/
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/

• Subtask 0: 0 / 0
• Subtask 1: 6 / 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