Submission #792037

#	Time	Username	Problem	Language	Result	Execution time	Memory
792037		I_Love_EliskaM_	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	1364 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
#define int ll 
const int inf=1e18;

int sq(int x) {
    return x*x;
}

struct sgt {

int pointer=0; //Keeps track of the best line from previous query
vector<long long> M; //Holds the slopes of the lines in the envelope
vector<long long> B; //Holds the y-intercepts of the lines in the envelope
//Returns true if either line l1 or line l3 is always better than line l2
bool bad(int l1,int l2,int l3)
{
    /*
    intersection(l1,l2) has x-coordinate (b1-b2)/(m2-m1)
    intersection(l1,l3) has x-coordinate (b1-b3)/(m3-m1)
    set the former greater than the latter, and cross-multiply to
    eliminate division
    */
    return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]);
}
//Adds a new line (with lowest slope) to the structure
void add(long long m,long long b)
{
    //First, let's add it to the end
    M.push_back(m);
    B.push_back(b);
    //If the penultimate is now made irrelevant between the antepenultimate
    //and the ultimate, remove it. Repeat as many times as necessary
    while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
    {
        M.erase(M.end()-2);
        B.erase(B.end()-2);
    }
}
//Returns the minimum y-coordinate of any intersection between a given vertical
//line and the lower envelope
long long query(long long x)
{
    //If we removed what was the best line for the previous query, then the
    //newly inserted line is now the best for that query
    if (pointer>=M.size())
        pointer=M.size()-1;
    //Any better line must be to the right, since query values are
    //non-decreasing
    while (pointer<M.size()-1&&
      M[pointer+1]*x+B[pointer+1]<M[pointer]*x+B[pointer])
        pointer++;
    return M[pointer]*x+B[pointer];
}

};

#define int ll
int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {

    vector<int> a(m,0);
    forn(i,n) {
        int x=r[i], y=c[i];
        if (x<y) {
            a[x]=max(a[x],y-x+1);
        } else {
            a[y]=max(a[y],x-y+1);
        }
    }
    int x=-inf;
    forn(i,m) {
        if (!a[i]) continue;
        if (a[i]+i<=x) a[i]=0;
        else x=a[i]+i;
    }
    int z=0;
    forn(i,m) z+=!!a[i];
    if (z<=k) {
        int ans=0;
        int last=-1;
        forn(i,m) {
            if (!a[i]) continue;
            if (last==-1) {
                ans+=a[i]*a[i];
                last=i;
                continue;
            }
            if (last + a[last] >= i) {
                ans += sq(a[i]) - sq(last+a[last]-i);
                last=i;
            } else {
                ans+=a[i]*a[i];
                last=i;
            }
        }
        return ans;
    }

    if (n*k > 1e7) return -1;
    vector<sgt> st(k+1);
    forn(i,k+1) st[i].add(0,inf);
    vector<pi> v;
    forn(i,m) if (a[i]) v.pb({i,i+a[i]});
    n=v.size();
    st[1].add(-2*v[0].f,sq(v[0].f));

    vector<int> dp(k+1,inf);
    dp[1]=sq(v[0].s - v[0].f);
 
    for (int i=1; i<n; ++i) {
        for (int j=min(1ll*k,i+1); j>0; --j) {
            int f=st[j].query(v[i].s) + sq(v[i].s);
            int s=dp[j-1] + sq(v[i].s-v[i].f);
            if (v[i-1].s > v[i].f) s-=sq(v[i-1].s-v[i].f);
            dp[j]=min(f,s);
            st[j].add(-2*v[i].f,sq(v[i].f)+s-sq(v[i].s-v[i].f));
        }
    }
    return dp[k];
    
}
#undef int

Compilation message (stderr)

aliens.cpp: In member function 'long long int sgt::query(long long int)':
aliens.cpp:54:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if (pointer>=M.size())
      |         ~~~~~~~^~~~~~~~~~
aliens.cpp:58:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while (pointer<M.size()-1&&
      |            ~~~~~~~^~~~~~~~~~~

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