Submission #592131

#	Time	Username	Problem	Language	Result	Execution time	Memory
592131		yutabi	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	312 KiB

aliens

#include "aliens.h"


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


#define pb push_back

typedef long long ll;
typedef pair <ll,ll> ii;


int par[200007];
int r[200007];


int find_parent(int a)
{
    if(par[a]==a)
    {
        return a;
    }

    return a=find_parent(par[a]);
}

void make_union(int a, int b)
{
    a=find_parent(a);
    b=find_parent(b);

    if(a==b)
    {
        return;
    }

    if(a>b)
    {
        swap(a,b);
    }

    par[b]=a;

    r[a]=r[b];
}



long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    int K=n;
    vector <ii> s;
    vector <ii> nw;

    for(int i=0;i<n;i++)
    {
        s.pb(ii(r[i],c[i]));
    }

    for(int i=0;i<n;i++)
    {
        if(s[i].first<s[i].second)
        {
            nw.pb(ii(s[i].second,s[i].first));
        }

        else
        {
            nw.pb(ii(s[i].first,s[i].second));
        }
    }

    s=nw;
    nw.clear();

    vector <ll> best(m,m*2);

    for(int i=0;i<s.size();i++)
    {
        best[s[i].first]=min(best[s[i].first],s[i].second);
    }

    for(int i=0;i<s.size();i++)
    {
        if(best[s[i].first]==s[i].second)
        {
            nw.pb(s[i]);

            best[s[i].first]--;
        }
    }

    s=nw;
    nw.clear();

    sort(s.begin(),s.end());

    for(int i=0;i<s.size();i++)
    {
        while(nw.size() && s[i].second<=nw.back().second)
        {
            nw.pop_back();
        }

        nw.push_back(s[i]);
    }

    s=nw;
    nw.clear();

    for(int i=0;i<s.size();i++)
    {
        //printf("%d %d\n",s[i].first,s[i].second);
    }

    ll ans=1;
    ans*=s[0].first-s[0].second+1;
    ans*=s[0].first-s[0].second+1;

    //printf("%lld\n",ans);

    priority_queue <pair <ll,ii> > pq;

    for(int i=0;i<s.size();i++)
    {
        par[i]=r[i]=i;
    }

    for(int i=1;i<s.size();i++)
    {
        ll ee=1;

        ee*=s[i-1].first-s[i].second+1;
        ee*=s[i-1].first-s[i].second+1;

        if(s[i].second>s[i-1].first)
        {
            ee=0;
        }

        ans-=ee;
        ans+=(s[i].first-s[i].second+1)*(s[i].first-s[i].second+1);

        pq.push(make_pair(-(((s[i].first-s[i-1].second+1)*(s[i].first-s[i-1].second+1))-((s[i].first-s[i].second+1)*(s[i].first-s[i].second+1))-((s[i-1].first-s[i-1].second+1)*(s[i-1].first-s[i-1].second+1))+(ee)),ii(i-1,i)));
    }

    K=s.size();

    //printf("%lld\n",K);

    while(K>n)
    {
        ll val=-pq.top().first;
        int fr=pq.top().second.first;
        int sc=pq.top().second.second;

        pq.pop();

        fr=find_parent(fr);
        sc=find_parent(sc);

        if(fr==sc)
        {
            continue;
        }

        ll ee=(s[fr].first-s[sc].second+1)*(s[fr].first-s[sc].second+1);

        if(s[sc].second>s[fr].first)
        {
            ee=0;
        }

        ll nw_val=(s[sc].first-s[fr].second+1)*(s[sc].first-s[fr].second+1);

        nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1);
        nw_val-=(s[sc].first-s[sc].second+1)*(s[sc].first-s[sc].second+1);

        nw_val+=ee;

        if(nw_val!=val)
        {
            continue;
        }

        ans+=val;

        make_union(fr,sc);

        s[fr].first=s[sc].first;


        int L=fr-1;
        int R=r[fr]+1;

        if(L>=0)
        {
            ee=(s[L].first-s[fr].second+1)*(s[L].first-s[fr].second+1);

            if(s[fr].second>s[L].first)
            {
                ee=0;
            }

            nw_val=(s[fr].first-s[L].second+1)*(s[fr].first-s[L].second+1);
            
            nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1);
            nw_val-=(s[L].first-s[L].second+1)*(s[L].first-s[L].second+1);

            nw_val+=ee;

            pq.push(make_pair(-nw_val,ii(L,fr)));
        }

        if(R<s.size())
        {
            ee=(s[fr].first-s[R].second+1)*(s[fr].first-s[R].second+1);
            
            nw_val=(s[R].first-s[fr].second+1)*(s[R].first-s[fr].second+1);

            nw_val-=(s[fr].first-s[fr].second+1)*(s[fr].first-s[fr].second+1);
            nw_val-=(s[R].first-s[R].second+1)*(s[R].first-s[R].second+1);

            nw_val+=ee;
            
            pq.push(make_pair(-nw_val,ii(fr,R)));
        }

        k--;
    }

    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i=1;i<s.size();i++)
      |                 ~^~~~~~~~~
aliens.cpp:216:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |         if(R<s.size())
      |            ~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40