Submission #773429

#	Time	Username	Problem	Language	Result	Execution time	Memory
773429		Amylopectin	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	352 KiB

aliens

#include "aliens.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long mxn = 1e6 + 10;
struct pri
{
    long long fi,se,are;
    bool operator () (const struct pri &l,const struct pri &r)
    {
        return l.are > r.are;
    }
};
struct we
{
    long long dip,hei;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dip < r.dip;
}

priority_queue <struct pri, vector<struct pri>, struct pri> qu;
struct we sot[mxn] = {},ta[mxn] = {};
long long sem[mxn] = {},u[mxn] = {},le[mxn] = {},ri[mxn] = {},leva[mxn] = {}
,riva[mxn] = {};
long long ab(long long l)
{
    if(l < 0)
        return -l;
    return l;
}
long long squ(long long l)
{
    return l*l;
}
// long long bui(long long cl,long long cr,long long no)
// {
//     if(cl == cr)
//     {
//         sem[i] = 1;
//         return 0;
//     }
//     long long mid = (cl+cr) / 2;
//     bui(cl,mid,no*2);
//     bui(mid+1,cr,no*2+1);
//     sem[no] = sem[no*2] + sem[no*2+1];
//     return 0;
// }
long long take_photos(int nn, int mm, int nnph
, std::vector<int> rr, std::vector<int> cc) 
{
    long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
    ,ru = 0,su = 0,care,fdip,fhei,cva,cfi,cse,ffi,fse,cl,cr;
    for(i=0; i<n; i++)
    {
        rr[i] ++;
        cc[i] ++;
        if(rr[i] > cc[i])
        {
            cn = rr[i];
            rr[i] = cc[i];
            cc[i] = cn;
        }
        sot[i] = {rr[i] + cc[i] - 1,cc[i] - rr[i]};
    }
    sort(sot,sot+n,cmp);
    ta[0] = {sot[0].dip,sot[0].hei};
    ru = 0;
    for(i=1; i<n; i++)
    {
        while(ru >= 0 && ta[ru].dip - ta[ru].hei >= sot[i].dip - sot[i].hei)
        {
            ru--;
        }
        if(ta[ru].dip + ta[ru].hei < sot[i].dip + sot[i].hei)
        {
            ru++;
            ta[ru] = {sot[i].dip,sot[i].hei};
        }
    }
    su += squ((ta[0].hei+1));
    le[0] = -1;
    ri[ru] = -1;
    for(i=1; i<=ru; i++)
    {
        cn = ta[i-1].dip + ta[i-1].hei;
        cm = ta[i].dip - ta[i].hei;
        if(cn >= cm)
        {
            fn = (cn-cm+2)/2;
            su -= squ(fn);
            cva = (ta[i-1].hei+1-fn) * (ta[i].hei+1-fn) * 2;
            qu.push({i-1,i,cva});
        }
        else 
        {
            fn = ((ta[i].dip + ta[i].hei) - (ta[i-1].dip - ta[i-1].hei) + 2)/2;
            cva = squ(fn) - squ(ta[i-1].hei+1) - squ(ta[i].hei+1);
            qu.push({i-1,i,cva});
        }
        su += squ((ta[i].hei+1));
        leva[i] = cva;
        riva[i-1] = cva;
        ri[i-1] = i;
        le[i] = i-1;
    }
    // bui(0,ru,1);
    for(i=0; i<=ru-nph; i++)
    {
        while(!qu.empty())
        {
            cfi = qu.top().fi;
            cse = qu.top().se;
            care = qu.top().are;
            qu.pop();
            if(u[cfi] != 0 || u[cse] != 0 || leva[cse] != care || riva[cfi] != care)
            {
                continue;
            }
            break;
        }
        su += care;
        fse = (ta[cse].dip + ta[cse].hei);
        ffi = ta[cfi].dip - ta[cfi].hei;
        fdip = (ffi+fse) / 2;
        fhei = (fse-ffi) / 2;
        ta[cfi].dip = fdip;
        ta[cfi].hei = fhei;
        u[cse] = 1;
        cl = le[cfi];
        cr = ri[cse];
        if(cl != -1)
        {
            cn = ta[cl].dip + ta[cl].hei;
            cm = fdip - fhei;
            if(cn >= cm)
            {
                fn = (cn-cm+2)/2;
                // su -= squ(fn);
                cva = (ta[cl].hei+1-fn) * (fhei+1-fn) * 2;
                qu.push({cl,cfi,cva});
            }
            else 
            {
                fn = ((fdip + fhei) - (ta[cl].dip - ta[cl].hei) + 2)/2;
                cva = squ(fn) - squ(ta[cl].hei+1) - squ(fhei+1);
                qu.push({cl,cfi,cva});
            }
            leva[cfi] = cva;
            riva[cl] = cva;
        }
        if(cr != -1)
        {
            cn = fdip + fhei;
            cm = ta[cr].dip - ta[cr].hei;
            if(cn >= cm)
            {
                fn = (cn-cm+2)/2;
                // su -= squ(fn);
                cva = (fhei+1-fn) * (ta[cr].hei+1-fn) * 2;
                qu.push({cfi,cr,cva});
            }
            else 
            {
                fn = ((ta[cr].dip + ta[cr].hei) - (fdip - fhei) + 2)/2;
                cva = squ(fn) - squ(fhei+1) - squ(ta[cr].hei+1);
                qu.push({cfi,cr,cva});
            }
            leva[cr] = cva;
            riva[cfi] = cva;
            le[cr] = cfi;
            ri[cfi] = cr;
        }
        else 
        {
            ri[cfi] = -1;
        }
        
    }
    return su;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:56:22: warning: unused variable 'm' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                      ^
aliens.cpp:56:43: warning: unused variable 'j' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                           ^
aliens.cpp:56:45: warning: unused variable 'k' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                             ^
aliens.cpp:56:56: warning: unused variable 'fm' [-Wunused-variable]
   56 |     long long n = nn,m = mm, nph = nnph,i,j,k,cn,cm,fn,fm
      |                                                        ^~
aliens.cpp:127:38: warning: 'cse' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |         fse = (ta[cse].dip + ta[cse].hei);
      |                              ~~~~~~~~^~~
aliens.cpp:128:37: warning: 'cfi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |         ffi = ta[cfi].dip - ta[cfi].hei;
      |                             ~~~~~~~~^~~
aliens.cpp:126:12: warning: 'care' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |         su += care;
      |         ~~~^~~~~~~

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