Submission #1274423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274423		scalifrastico_098	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std; 
int n1, k1; vector<long long> lr, rr;
struct l
{
    long long m, b; int f, cnt;
};
struct ch
{
    deque<l>dq; 
    long long ev(const l& li, long long x){return li.m*x+li.b;}
    bool ba(const l& l1, const l& l2, const l& l3)
    {
        return (l3.b-l1.b)*(l1.m-l2.m)<=(l2.b-l1.b)*(l1.m-l3.m);
    }
    void add(l li)
    {
        while(dq.size()>=2&&ba(dq[dq.size()-2], dq.back(), li)) dq.pop_back();
        dq.push_back(li);
    }
    pair<long long, int> query(long long x)
    {
        while(dq.size()>=2)
        {
            long long a=ev(dq[0], x), b=ev(dq[1], x); if(a>b) dq.pop_front();
            else if(a==b){if(dq[1].cnt<=dq[0].cnt)dq.pop_front();else break;}
            else break;
        }
        return {ev(dq[0], x), dq[0].f};
    }
};

pair<long long, int> p(long long pen)
{
    auto adj=[&](long long i)
    {
        if(i==1) return 0LL; return max(0LL, rr[i-1]-lr[i]+1)*max(0LL, rr[i-1]-lr[i]+1);
    };
    vector<long long> g(n1+1, 0); vector<int> mf(n1+1, 0); g[0]=0; mf[0]=0;
    ch hull; hull.add({-2*lr[1], lr[1]*lr[1]-2LL*lr[1]+pen, 0, 0});
    for(long long i=1; i<=n1; i++)
    {
        long long ans=rr[i-1];
        pair<long long, int> uj=hull.query(ans);
        g[i]=ans*ans+2LL*ans+1+uj.first;
        mf[i]=mf[uj.second]+1;
        long long mt=-2LL*(lr[i]-1), nt=g[i]+(lr[i])*(lr[i])-adj(i)+pen;
        hull.add({mt, nt, (int)i, mf[i]});
    }
    return {g[n1], mf[n1]};
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    long long jk=-1;
    if(n==0) return 0; vector<pair<long long, long long>> a(n);
    vector<long long> ul, tra;
    for(long long i=0; i<n; i++)
    {
        a[i]={min(r[i], c[i]),max(r[i], c[i])};
    } 
    sort(a.begin(), a.end(), [](const pair<long long, long long>& a, const pair<long long, long long>& b)
    {
        if(a.first!=b.first) return a.first<b.first; return a.second>b.second;
    });
    for(auto &x: a)
    {
        if(x.second<=jk) continue; ul.push_back(x.first); tra.push_back(x.second);
        jk=x.second;
    }
    n1=ul.size();k1=min(k, n1); lr.assign(n1+1, 0); rr.assign(n1+1, 0);
    for(long long i=1; i<=n1; i++)
    {
        lr[i]=ul[i-1]; rr[i]=tra[i-1];
    }
    rr[0]=0;
    auto adj=[&](long long i)
    {
        if(i==1) return 0LL; return max(0LL, rr[i-1]-lr[i]+1)*max(0LL, rr[i-1]-lr[i]+1);
    };
    long long l1=0, r2=1LL*m*m; 
    while(l1<r2)
    {
        long long mi=(l1+r2)/2; pair<long long, int> u=p(mi);
        if(u.second>k){l1=mi+1;} else r2=mi; 
    }
    pair<long long, int> a2=p(l1), b; if(l1==0)b=p(0); else b=p(l1-1);
    long long ans=a2.first-l1*1LL*k, ans1; if(l1==0){ans1=b.first;} else ans1=b.first-(l1-1)*1LL*k;
    return min(ans, ans1);
} 

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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