Submission #765126

#	Time	Username	Problem	Language	Result	Execution time	Memory
765126		oneloveforever	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	320 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<ll,ll>
const ll inf=1e18+7;
ll n,m,k;
vector<ii>poll;
ll power(ll x)
{
    return x*x;
}
struct node
{
    ll x,y,num;
    node(ll _x=0,ll _y=0,ll _num=0)
    {
        x=_x,y=_y,num=_num;
    }
};
bool check(node a,node b,node c)
{
    //double value_x=(b.y-a.y)/(a.x-b.x);
    //double value_y=(c.y-b.y)/(b.x-c.x);
    ll value_x=(b.y-a.y)*(b.x-c.x);
    ll value_y=(c.y-b.y)*(a.x-b.x);
    return (value_x<=value_y);
}
ii get(ll x,node need)
{
    ii ans;
    ans.x=need.x*x+need.y;
    ans.y=need.num;
    return ans;
}

ii calc(ll constant)
{
    ii trace=make_pair(0,0);
    deque<node>convex;
    for(ll i=n-1;i>=0;i--)
    {
        ll used=power(max((ll)0,poll[i].y-poll[i+1].x+1));
        node path=node(-2*(poll[i].y+1),trace.x+power(poll[i].y+1)-used,trace.y);
        while(convex.size()>=2&&!check(convex[convex.size()-2],convex[convex.size()-1],path))convex.pop_back();
        convex.push_back(path);
        ll C=poll[i].x;
        while(convex.size()>=2&&get(C,convex[0])>=get(C,convex[1]))convex.pop_front();
        ii need=get(C,convex[0]);
        //cout<<need.x<<" "<<need.y<<endl;
        trace.x=need.x+power(poll[i].x)+constant;
        trace.y=need.y+1;
        //cout<<trace.x<<" "<<trace.y<<" "<<constant<<endl;
        //cout<<trace.x<<" "<<trace.y<<" "<<power(poll[i].x)+constant<<" "<<need.x<<" "<<need.y<<endl;
    }
    return trace;
}
bool cmp(ii a,ii b)
{
    if(a.x==b.x)return a.y>b.y;
    return a.x<b.x;
}
ll take_photos(int _n,int _m,int _k,vector<int>r,vector<int>c)
{
    n=_n;
    m=_m;
    k=_k;
    vector<ii>block;
    for(ll i=1;i<=n;i++)
    {
        ll x=min(r[i-1],c[i-1]);
        ll y=max(r[i-1],c[i-1]);
        block.push_back({x,y});
    }
    sort(block.begin(),block.end(),cmp);
    block.resize(unique(block.begin(),block.end())-block.begin());

    vector<ll>q;
    for(ll i=n-1;i>=0;i--)
    {
        while(!q.empty()&&block[q.back()].y<=block[i].y)q.pop_back();
        q.push_back(i);
    }
    reverse(q.begin(),q.end());
    for(ll index:q)poll.push_back({block[index].x,block[index].y});
    n=(ll)poll.size();
    poll.push_back({m,m});
    //for(ii node:poll)cout<<node.x<<" "<<node.y<<endl;
    k=min(k,n);
    ll x=0;
    ll y=m*m+1;
    ll res=m*m;
    for(ll cnt=0;cnt<=50;cnt++)
    {
        ll mid=(x+y)/2;
        ii ans=calc(mid);
        if(ans.y<=k)
        {
            res=mid;
            y=mid;
        }
        else x=mid;
    }
    ii ans=calc(res);
    return ans.x-k*res;
}

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