Submission #567400

#	Time	Username	Problem	Language	Result	Execution time	Memory
567400		gs15120	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	320 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll long long//__int128
#define pii pair<int,int>
#define f first
#define s second
# define PI 3.14159265358979323846
#include <ext/pb_ds/assoc_container.hpp>

const ll mod=1000000007,div2=(mod+1)/2,inf=1987654321987654321;
using namespace __gnu_pbds;

struct chash_key
{
    ll operator()(pii x) const { return (ll)x.first*1000000000   + x.second; }
};
//gp_hash_table<pii,int,chash_key> hs[2],p[2];

struct P
{
    int x,y;
    /*bool operator <(const P &a) const
    {

        //if(y!=a.y)
        //return y<a.y;

        return y>a.y;
    }*/
};
struct L
{
    ll a,b;
    int n;
    ll sol(ll x)
    {
        return a*x+b;
    }
};

struct LI
{
    int x,y;
    L l={0,inf};
};

int a,b,c,d;


int dx[10]={1,0,-1,0,-1,1,-1,1},dy[11]={0,1,0,-1,-1,-1,1,1},sx[4]={0,1,0,1},sy[4]={0,0,1,1};
ll x,y,z,rv,lv;
int o[111111];

vector<LI> li;
void add(int i,int n,int m,L l)
{
    int h=(n+m)/2;
    if(l.sol(h)<li[i].l.sol(h))
    {
        swap(l,li[i].l);
    }
    L s=li[i].l;
    if(l.sol(n)<s.sol(n))
    {
        if(!li[i].x)
        {
            li[i].x=li.size();
            li.push_back({});
        }
        add(li[i].x,n,h,l);
    }
    if(l.sol(m)<s.sol(m))
    {
        if(!li[i].y)
        {
            li[i].y=li.size();
            li.push_back({});
        }
        add(li[i].y,h+1,m,l);
    }
}

L get(int i,int n,int m,int k)
{
    if(!i||m<k||n>k) return {0,inf,0};
    L l=li[i].l;
    if(n==m) return l;
    L s;
    if(k<=(n+m)/2) s=get(li[i].x,n,(n+m)/2,k);
    else s=get(li[i].y,(n+m)/2+1,m,k);
    if(l.sol(k)<s.sol(k)) return l;
    return s;
}

int f(ll v)
{
    li.clear();
    li.push_back({});
    li.push_back({0,0,{0,0,0}});
    int ff=0;
    for(int t=1;t<=a;t++)
    {
        L l=get(1,1,100000,t);
        ff=l.n+1;
        z=l.sol(t)+(ll)t*t+v;
        add(1,1,100000,{-2*o[t],z+(ll)o[t]*o[t],l.n+1});
    }

    return ff;
}

ll take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
    b=n;
    a=m;
    for(int t=1;t<=a;t++) o[t]=t;
    for(int t=1;t<=b;t++)
    {
        o[max(r[t],c[t])]=min(min(r[t],c[t]),o[max(r[t],c[t])]);
    }
    for(int t=a-1;t;t--)
        o[t]=min(o[t],o[t+1]);
    ll s=0,e=100000000000;
    int x=0,y=a+1;
    for(;s<=e;)
    {
        ll h=(s+e)/2;
        int ff=f(h);
        if(ff==k) return z-k*h;
        if(ff<k)
        {
            if(x<ff) x=ff,lv=z-k*h;
            s=h+1;
        }
        else
        {
            if(y>ff) y=ff,rv=z-k*h;
            e=h-1;
        }
    }
    return rv+(lv-rv)/(y-x)*(y-k);
}

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