Submission #824933

#	Time	Username	Problem	Language	Result	Execution time	Memory
824933		vnm06	Aliens (IOI16_aliens)	C++14	100 / 100	101 ms	9008 KiB

aliens

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

struct line
{
    long long res, cf, tm;
    long long brp;
    line() {}
    line(long long a, long long b, long long c, long long d)
    {
        res=a;
        cf=b;
        tm=c;
        brp=d;
    }
};

long long N;
pair<long long, long long> pr[100005];

long long id=0;
long long T, ans, totbr;
vector<line> lines;

void add_line(long long k)
{
    long long res, br, tm, cf;
    while(id!=lines.size()-1 && lines[id+1].tm<=pr[k].second) id++;
        res=lines[id].res+(pr[k].second-lines[id].cf+1)*(pr[k].second-lines[id].cf+1)+T;
        br=lines[id].brp+1;

    if(k==N-1)
    {
        ans=res;
        totbr=br;
    }
    else
    {
        cf=pr[k+1].first;
        if(cf<=pr[k].second) res-=(pr[k].second-cf+1)*(pr[k].second-cf+1);
        long long tN=lines.size();
        while(tN>id)
        {
            long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf;
            if((vr-cf+1)*(vr-cf+1)+res<=(vr-cf2+1)*(vr-cf2+1)+res2) tN--;
            else break;
        }
        lines.resize(tN);
        if(tN==id) lines.push_back(line(res, cf, -1, br));
        else
        {
            long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf, tm;
            tm=(res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)/(2*cf-2*cf2);
            if((res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)%(2*cf-2*cf2)) tm++;
            lines.push_back(line(res, cf, tm, br));
        }
    }
}

pair<long long, long long> solve()
{
    id=0;
    lines.resize(0);
    lines.push_back(line(0, pr[0].first, -1, 0));
    for(long long i=0; i<N; i++) add_line(i); ///cout<<lines[lines.size()-1].res<<' '<<lines[lines.size()-1].cf<<" "<<lines[lines.size()-1].brp<<endl;}
    return {totbr, ans};
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    N=n;
    for(int i=0; i<n; i++) if(r[i]>c[i]) swap(r[i], c[i]);
    for(int i=0; i<n; i++) pr[i]={r[i], c[i]};
    sort(pr, pr+N);
    long long id=0;
    for(long long i=1; i<N; i++)
    {
        if(pr[i].second<=pr[id].second) continue;
        if(pr[i].first!=pr[id].first) id++;
        swap(pr[id], pr[i]);
    }
    N=n=id+1;
    k=min(k, n);
    ///for(long long i=0; i<n; i++) cout<<pr[i].first<<" "<<pr[i].second<<endl;
    long long le=0, ri=1e12;
    while(ri-le>1)
    {
        long long mid=(le+ri)/2;
        T=mid;
        pair<long long, long long> pr=solve();
        ///cout<<T<<" "<<pr.second<<" "<<pr.first<<endl;
        if(pr.first==k) return pr.second-mid*k;
        else if(pr.first<k) ri=mid;
        else le=mid;
    }
        T=le;
        pair<long long, long long> pr=solve();
    return pr.second-T*k;
}

Compilation message (stderr)

aliens.cpp: In function 'void add_line(long long int)':
aliens.cpp:29:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(id!=lines.size()-1 && lines[id+1].tm<=pr[k].second) id++;
      |           ~~^~~~~~~~~~~~~~~~
aliens.cpp:53:23: warning: unused variable 'vr' [-Wunused-variable]
   53 |             long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf, tm;
      |                       ^~
aliens.cpp:28:24: warning: unused variable 'tm' [-Wunused-variable]
   28 |     long long res, br, tm, cf;
      |                        ^~

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