Submission #171582

#	Time	Username	Problem	Language	Result	Execution time	Memory
171582		mhy908	Aliens (IOI16_aliens)	C++14	0 / 100	3 ms	504 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
pll point[100010], arr[100010];
int n, m, k, r;
LL la[100010], lb[100010], dp[100010];
int num[100010], dpnum[100010];
int sz, p;
double cross(int x, int y){return (double)(lb[y]-lb[x])/(la[x]-la[y]);}
void in(LL p, LL q){
    la[sz]=p;
    lb[sz]=q;
    num[sz]=++r;
    while(sz>1&&cross(sz-1,sz-2)>cross(sz-1,sz)){
        la[sz-1]=la[sz];
        lb[sz-1]=lb[sz];
        num[sz-1]=num[sz];
        sz--;
    }
    sz++;
}
LL query(LL x){
    while(p+1<sz&&cross(p, p+1)<=x)p++;
    return lb[p]+la[p]*x;
}
void get_dp(LL cc){
    sz=p=r=0;
    in(-2*arr[1].F, arr[1].F*arr[1].F);
    dpnum[1]=1;
    dp[1]=(arr[1].F-arr[1].S+1)*(arr[1].F-arr[1].S+1);
    for(int i=2; i<=n; i++){
        dp[i]=query(arr[i].S+1)+(arr[i].S+1)*(arr[i].S+1)-cc;
        dpnum[i]=dpnum[num[p]]+1;
        in(-2*arr[i].F, arr[i].S*arr[i].S+dp[i-1]);
    }
}
LL Solve(){
    LL l=0, r=(LL)m*m+2000;
    while(l<r){
        LL mid;
        if(l+1==r)mid=r;
        else mid=(l+r)/2+1;
        get_dp(2*mid+1);
        if(dpnum[n]<k)r=mid-1;
        else l=mid;
    }
    get_dp(2*l+1);
    int k1=dpnum[n];
    LL p1=dp[n]+(LL)dpnum[n]*(2*l+1);
    get_dp(2*l+3);
    int k2=dpnum[n];
    LL p2=dp[n]+(LL)dpnum[n]*(2*l+3);
    return (p2*(LL)(k1-k)+p1*(LL)(k-k2))/(LL)(k1-k2);
}
LL take_photos(int _n, int _m, int _k, vector<int> rr, vector<int> c) {
    n=_n, m=_m, k=_k;
    for(int i=0; i<n; i++){
        if(rr[i]>c[i])swap(rr[i], c[i]);
        point[i+1]=mp((LL)rr[i]+1, (LL)c[i]+1);
    }
    sort(point+1, point+n+1);
    LL maxx=0;
    for(int i=1; i<=n; i++){
        if(maxx<point[i].S){
            maxx=point[i].S;
            if(arr[r].F<point[i].F&&arr[r].S<point[i].S)arr[++r]=point[i];
            else arr[r]=point[i];
        }
    }
    n=r;
    for(int i=1; i<=n; i++){
        arr[i].F*=2;
        arr[i].S*=2;
    }
    return Solve();
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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