Submission #1149089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149089		Rares	Nile (IOI24_nile)	C++20	0 / 100	40 ms	12472 KiB

nile

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

using namespace std;
/*ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout*/

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

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;
};
vector<dif> d;
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[2][MAXN],sum[MAXN],l[MAXN],dmine[2][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);

    ll dcrt[2],dcrte[2];
    if (s[x]%2){
        dcrt[0]=min (dmin[0][x],dmin[1][y]);
        dcrt[1]=min (dmin[1][x],dmin[0][y]);

        dcrte[0]=min (dmine[0][x],dmine[1][y]);
        dcrte[1]=min (dmine[1][x],dmine[0][y]);
    }
    else{
        dcrt[0]=min (dmin[0][x],dmin[0][y]);
        dcrt[1]=min (dmin[1][x],dmin[1][y]);

        dcrte[0]=min (dmine[0][x],dmine[1][y]);
        dcrte[1]=min (dmine[1][x],dmine[0][y]);
    }
    if (s[x]<s[y]) swap (x,y);
    rez-=sum[x];
    rez-=sum[y];
    l[x]=min (l[x],l[y]);
    s[x]+=s[y];
    tata[y]=x;
    sumc2[x]+=sumc2[y];
    dmin[0][x]=dcrt[0];
    dmin[1][x]=dcrt[1];
    dmine[0][x]=dcrte[0];
    dmine[1][x]=dcrte[1];

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

    rez+=sum[x];
}
void enable (int x){
    int r=radacina (x);

    if ((x-l[r])%2==0) dmine[1][r]=min (dmine[1][r],1LL*a[x].c1-a[x].c2);
    else dmine[0][r]=min (dmine[0][r],1LL*a[x].c1-a[x].c2);
    rez-=sum[r];
    sum[r]=sumc2[r]+min (dmin[1][r],dmine[0][r]);
    rez+=sum[r];
}

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.push_back ({a[i+1].w-a[i].w,i,i+1});
        if (i<n-1) d.push_back ({a[i+2].w-a[i].w,i,i+2});
    }
    sort (d.begin (),d.end (),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;
        dmine[0][i]=dmine[1][i]=INF;
        dmin[0][i]=INF;
        dmin[1][i]=a[i].c1-a[i].c2;
        l[i]=i;
    }

    int j=0;

    for (int i=1;i<=m;++i){
        while (j<d.size () and q[i].x>=d[j].x){

            if (d[j].l+1==d[j].r) unire (d[j].l,d[j].r);
            else enable (d[j].l+1);
            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;
    for (int i=1;i<=n;++i){
        int x,y,z;
        cin >>x>>y>>z;
        W.push_back (x);
        A.push_back (y);
        B.push_back (z);
    }

    cin >>q;
    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<<'\n';
    }
    return 0;
}*/
/*
15 12 2 10 21
5 4 5 6 3
1 2 2 3 2
5 9 1

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: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18