Submission #853579

#	Time	Username	Problem	Language	Result	Execution time	Memory
853579		abcvuitunggio	Aliens (IOI16_aliens)	C++17	100 / 100	177 ms	20416 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define fi first
#define se second
using namespace std;
const int INF=1e18;
int n,dp[100001],s[100001],e[100001],mn[100001],mx[1000001],pos[100001],cnt[100001];
vector <pair <int, int>> v,ve;
int ce(int a, int b){
    return a/b-(((a<0&&b>0)||(a>0&&b<0))&&a/b*b!=a);
}
ld intersection(pair <int, int> p, pair <int, int> p2){
    if (p.fi==p2.fi)
        return (p2.se>p.se?INF:-INF);
    return ((ld)(p2.se-p.se))/(p.fi-p2.fi);
}
void add(pair <int, int> p, int i){
    while (v.size()>1){
        ld p12=intersection(v[v.size()-2],v.back()),p13=intersection(v[v.size()-2],p);
        if (p12>p13)
            break;
        v.pop_back();
        if (!ve.empty())
            ve.pop_back();
    }
    if (!v.empty()&&(v.back().fi==p.fi))
        return;
    if (!v.empty())
        ve.push_back({ce(p.se-v.back().se,v.back().fi-p.fi),v.size()});
    pos[v.size()]=i;
    v.push_back(p);
}
pair <int, int> get(int x){
    int l=0,r=((int)ve.size())-1,kq=0;
    while (l<=r){
        int mid=(l+r)>>1;
        if (ve[mid].fi>=x){
            kq=ve[mid].se;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return {v[kq].fi*x+v[kq].se,pos[kq]};
}
pair <int, int> check(int x){
    v.clear();
    ve.clear();
    for (int i=n-1;i>=0;i--){
        add({-2*(e[i]+1),dp[i+1]+mn[i]*(e[i]*2-mn[i]+2)+x},i);
        auto [v,j]=get(s[i]);
        dp[i]=v+s[i]*s[i];
        cnt[i]=cnt[j+1]+1;
    }
    return {dp[0],cnt[0]};
}
long long take_photos(int32_t N, int32_t M, int32_t K, vector <int32_t> R, vector <int32_t> C){
    memset(mx,-1,sizeof(mx));
    for (int i=0;i<N;i++)
        mx[min(R[i],C[i])]=max(mx[min(R[i],C[i])],(int)max(R[i],C[i]));
    for (int i=0;i<M;i++)
        if (mx[i]!=-1)
            ve.emplace_back(i,mx[i]);
    sort(ve.begin(),ve.end());
    int cur=-1;
    for (auto [i,j]:ve)
        if (j>cur){
            s[n]=i;
            e[n]=j;
            n++;
            cur=j;
        }
    s[n]=INF;
    K=min(K,(int32_t)n);
    for (int i=0;i<n;i++)
        mn[i]=min(s[i+1],e[i]+1);
    int l=0,r=1e12,kq=-1;
    while (l<=r){
        int mid=(l+r)/2;
        auto [mx,c]=check(mid);
        if (c>=K){
            kq=mx-K*mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return kq;
}

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