Submission #1221341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221341		Szymon_Pilipczuk	Aliens (IOI16_aliens)	C++20	0 / 100	10 ms	328 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e12;
vector<pair<int,int>> t;
vector<pair<ll,ll>> co;
int cn;
ll sq(ll a)
{
    return a*a;
}
vector<vector<ll>> tr;
void add(int p,ll a,ll b,int k)
{
    ll c = tr[p][0], d = tr[p][1], e = tr[p][2],l = tr[p][3],r = tr[p][4];
    if(c*(l+r)/2 + d > a*(l+r)/2 + b)
    {
        tr[p][0] = a;
        tr[p][1] = b;
        tr[p][2] = k;
        a = c;
        b = d;
        k = e;
        c = tr[p][0];
        d = tr[p][1];
        e = tr[p][2];
    }
    if(c*l + d > a*l + b)
    {
        if(tr[p][5] != -1)
        {
            add(tr[p][5],a,b,k);
        }
        else if(l <= (l+r)/2-1)
        {
            tr[p][5] = tr.size();
            tr.pb({a,b,k,l,(l+r)/2-1,-1,-1});
        }
    }
    else
    {
        if(tr[p][6] != -1)
        {
            add(tr[p][6],a,b,k);
        }
        else if((l+r)/2+1<=r)
        {
            tr[p][6] = tr.size();
            tr.pb({a,b,k,(l+r)/2+1,r,-1,-1});
        }
    }
}
pair<ll,ll> check(int p,ll c)
{
    ll l = tr[p][3],r = tr[p][4];
    pair<ll,ll> ans = {tr[p][0]*c+tr[p][1],tr[p][2]};
    //cerr<<tr[p][0]<<" "<<tr[p][1]<<" "<<tr[p][2]<<" "<<p<<" "<<c<<" a\n";
    if(c < (l+r)/2 && tr[p][5] != -1)
    {
        pair<ll,ll> cu = check(tr[p][5],c);
        if(cu.st < ans.st)
        {
            ans = cu;
        }
    }
    else if((l+r)/2 < c && tr[p][6] != -1)
    {
        pair<ll,ll> cu = check(tr[p][6],c);
        if(cu.st < ans.st)
        {
            ans = cu;
        }
    }
    return ans;
}
pair<ll,ll> solve(ll c)
{
    tr.clear();
    tr.pb({-2 * co[0].st,sq(co[0].st),0,0,infl,-1,-1});
    vector<pair<ll,ll>> ans(cn);
    rep(i,cn)
    {
        ans[i] = {check(0,co[i].nd+1).st + sq(co[i].nd+1) + c,check(0,co[i].nd+1).nd+1};
        if(i != cn-1) add(0,-2 * co[i+1].st,ans[i].st + sq(co[i+1].st) ,ans[i].nd);
        //cerr<<c<<" "<<co[i+1].st<<" "<<ans[i].st<<" "<<ans[i].nd<<" "<<i<<"\n";
    }
    return {ans[cn-1].st - ans[cn-1].nd*c,ans[cn-1].nd};
}
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
    rep(i,n)
    { 
        if(r[i] > c[i])
        {
            swap(r[i],c[i]);
        }
        t.pb({r[i],c[i]});
    }
    sort(all(t));
    int mxc = -1;
    rep(i,n)
    {
        if(i != n-1 && t[i].st == t[i+1].st)
        {
            continue;
        }
        if(t[i].nd > mxc)
        {
            co.pb(t[i]);
            mxc = t[i].nd;
        }
    }
    cn = co.size();
    ll l = -1;
    ll rr = infl;
    pair<ll,ll> cl;
    ll cc;
    //cerr<<endl<<endl;
    while(l + 1 < rr)
    {
        ll mid = (l+rr)/2;
        pair<ll,ll> cu = solve(mid);
        cl = cu;
        cc = mid;
        if(cu.nd < k)
        {
            rr = mid;
        }
        else if(cu.nd > k)
        {
            l = mid;
        }
        else
        {
            //cout<<cu.st<<"\n";
            return cu.st;
        }
    }
    //cerr<<cl.nd<<" "<<cc<<" "<<cl.st<<"\n";
    return cl.st + cc * (cl.nd-k);
}
/*int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> r,c;
    rep(i,n)
    {
        int a,b;
        cin>>a>>b;
        r.pb(a);
        c.pb(b);
    }
    cout<<take_photos(n,m,k,r,c);
}*/

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