Submission #1116907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116907		LeonidCuk	Nile (IOI24_nile)	C++17	100 / 100	98 ms	22968 KiB

nile

#include <bits/stdc++.h>
using namespace std;
struct torta
{
    long long int a,b,w;
};
struct que
{
    int k,id;
};
vector<torta>v,g;
vector<que>q;
vector<long long int>dsu,ssum,smax1,smax2,sz,ans;
long long int res=0;
long long int gsum(int i)
{
    if(sz[i]%2==0)
    {
        return ssum[i];
    }
    return ssum[i]-smax1[i];
}
int vfind(int a)
{
    if(a==dsu[a])return a;
    return dsu[a]=(vfind(dsu[a]));
}
bool cmp(torta &a,torta &b)
{
    return a.w<b.w;
}
bool cmp1(que &a,que &b)
{
    return a.k<b.k;
}
vector<long long> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E)
{
    int n,m;
    n=W.size();
    m=E.size();
    torta temp;
    que temp1;
    for(int i=0;i<n;i++)
    {
        temp.w=W[i];
        temp.a=A[i];
        temp.b=B[i];
        res+=A[i];
        v.push_back(temp);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<n;i++)
    {
        if(i>0)
        {
            temp.a=i-1;
            temp.b=i;
            temp.w=v[i].w-v[i-1].w;
            g.push_back(temp);
        }

        dsu.push_back(i);
        sz.push_back(1);
        smax1.push_back(v[i].a-v[i].b);
        ssum.push_back(v[i].a-v[i].b);
        smax2.push_back(INT_MAX);
        if(i>1)
        {
            temp.b=i-1;
            temp.w=v[i].w-v[i-2].w;
            g.push_back(temp);
        }
    }
    sort(g.begin(),g.end(),cmp);
    ans.resize(m);
    for(int i=0;i<m;i++)
    {
        temp1.k=E[i];
        temp1.id=i;
        q.push_back(temp1);
    }
    sort(q.begin(),q.end(),cmp1);
    int l=0,l1=0;
    while(l<g.size()||l1<q.size())
    {
        if(l1==q.size())break;
        if(l==g.size()||g[l].w>q[l1].k)
        {
            ans[q[l1].id]=res;
            l1++;
            continue;
        }
        if(g[l].a==g[l].b)
        {
            int a=vfind(g[l].a);
            res=res+gsum(a);
            smax1[a]=min(smax1[a],v[g[l].a].a-v[g[l].a].b);
            smax2[a]=min(smax2[a],v[g[l].a].a-v[g[l].a].b);
            res=res-gsum(a);
        }
        else
        {
            int a=vfind(g[l].a),b=vfind(g[l].b);
            res=res+gsum(a);
            res=res+gsum(b);
            dsu[b]=a;
            if(sz[a]%2==0)
            {
                smax1[a]=min(smax1[a],smax1[b]);
                smax2[a]=min(smax2[a],smax2[b]);
            }
            else
            {
                smax1[a]=min(smax1[a],smax2[b]);
                smax2[a]=min(smax2[a],smax1[b]);
            }
            sz[a]+=sz[b];
            ssum[a]+=ssum[b];
            res=res-gsum(a);
        }
        l++;
    }
    return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:84:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<torta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while(l<g.size()||l1<q.size())
      |           ~^~~~~~~~~
nile.cpp:84:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while(l<g.size()||l1<q.size())
      |                       ~~^~~~~~~~~
nile.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if(l1==q.size())break;
      |            ~~^~~~~~~~~~
nile.cpp:87:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<torta>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         if(l==g.size()||g[l].w>q[l1].k)
      |            ~^~~~~~~~~~

• 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