Submission #937983

#	Time	Username	Problem	Language	Result	Execution time	Memory
937983		DobromirAngelov	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

const int MAXN=1e5+5;
const long long INF=1e18;

struct Line
{
    long long k,n;
    long long st;
    int num;
    Line() {};
    Line(long long _k,long long _n,long long _st,int _num)
    {
        k=_k;
        n=_n;
        st=_st;
        num=_num;
    }
};

int n,m,k;
pair<int,int> tmp[MAXN];
vector<pair<int,int> > a;
long long dp[MAXN];
int seg[MAXN];
Line lines[MAXN];
int beg=0, en=-1;

long long crossX(Line a,Line b)
{
    long long diffK=a.k-b.k;
    long long diffN=b.n-a.n;
    if(diffK==0)
    {
        if(a.n>b.n) return INF;
        else return 0;
    }
    return (diffN+diffK-1)/diffK;
}

void addLine(Line cur)
{
    while(en-beg+1>0 && crossX(lines[en], cur)<=lines[en].st) en--;
    if(en-beg+1>0) cur.st=crossX(lines[en], cur);
    lines[++en]=cur;
}

pair<int,long long> query(long long x)
{
    while(en-beg+1>1 && lines[beg+1].st<=x) beg++;
    return {lines[beg].num, lines[beg].k*x+lines[beg].n};
}

void resetLines()
{
    beg=0;
    en=-1;
}

int solve(long long pen)
{
    resetLines();
    dp[0]=0;
    seg[0]=0;
    for(int i=1;i<=n;i++)
    {
        long long x=a[i].fi, y=a[i].se;
        long long t=max(0LL, a[i-1].se-x+1);
        addLine(Line(-(x-1)*2, (x-1)*(x-1)-t*t+dp[i-1]+pen, 0, i));
        pair<int,long long> qr=query(a[i].se);
        dp[i]=qr.se+a[i].se*a[i].se;
        seg[i]=seg[qr.fi-1]+1;
    }
    return seg[n];
}

long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c)
{
    n=_n; m=_m; k=_k;
    for(int i=0;i<n;i++)
    {
        _r[i]++; _c[i]++;
        if(_r[i]>_c[i]) swap(_r[i], _c[i]);
        tmp[i+1].fi=_r[i], tmp[i+1].se=_c[i];
    }

    sort(tmp+1,tmp+n+1,[](pair<int,int> x,pair<int,int> y)
         {
             if(x.fi==y.fi) return x.se>y.se;
             return x.fi<y.fi;
         });
    a.push_back({0,0});
    for(int i=1;i<=n;i++)
    {
        if(tmp[i].fi>a.back().fi && tmp[i].se>a.back().se) a.push_back(tmp[i]);
    }
    n=a.size()-1;

    k=min(k,n);
    long long l=0,r=1e18;
    while(l<r)
    {
        long long mid=(l+r+1)/2;
        if(solve(mid)>=k) l=mid;
        else r=mid-1;
    }

    int segs=solve(l);
    long long ans=dp[n]-k*l;
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int solve(long long int)':
aliens.cpp:73:30: warning: unused variable 'y' [-Wunused-variable]
   73 |         long long x=a[i].fi, y=a[i].se;
      |                              ^
aliens.cpp: In function 'long long int take_photos(long long int, long long int, long long int, std::vector<long long int>, std::vector<long long int>)':
aliens.cpp:114:9: warning: unused variable 'segs' [-Wunused-variable]
  114 |     int segs=solve(l);
      |         ^~~~
/usr/bin/ld: /tmp/cc7PPqrs.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status