제출 #1221991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221991		Szymon_Pilipczuk	Aliens (IOI16_aliens)	C++20	100 / 100	252 ms	12572 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;
deque<vector<ll>> dq;
void add(ll a,ll b,int k)
{
    if(dq.size() == 0)
    {
        dq.push_back({0,infl,a,b,k});
        return;
    }
    vector<ll> c = dq.back();
    if(c[2] == a)
    {
        if(c[3] > b || (c[3] == b && c[4] < k))
        {
            dq.pop_back();
            add(a,b,k);
        }
    }
    else
    {
        ll cu = (b-c[3])/(c[2]-a) + 1;
        bool r = ((b-c[3])%(c[2]-a) == 0 && c[4] < k);
        if(cu <= c[0] || (c[0] + 1 == cu && r))
        {
            dq.pop_back();
            add(a,b,k);
        }
        else
        {
            if(r)
            {
                cu--;
            }
            dq.back()[1] = cu-1;
            dq.pb({cu,infl,a,b,k});
        }
    }
}
pair<ll,ll> check(ll c)
{
    if(dq.front()[1] >=c)
    {
        return {c * dq.front()[2] + dq.front()[3],dq.front()[4]};
    }
    else
    {
        dq.pop_front();
        return check(c);
    }
}
pair<ll,ll> solve(ll c)
{
    dq.clear();
    add(-2 * co[0].st,sq(co[0].st),0);
    vector<pair<ll,ll>> ans(cn);
    rep(i,cn)
    {
        ans[i] = {check(co[i].nd+1).st + sq(co[i].nd+1) + c,check(co[i].nd+1).nd+1};
        if(i != cn-1) add(-2 * co[i+1].st,ans[i].st + sq(co[i+1].st) - sq(max(co[i].nd -co[i+1].st+1,0LL)) ,ans[i].nd);
        //<<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;
    //cerr<<endl<<endl;
    while(l + 1 < rr)
    {
        ll mid = (l+rr)/2;
        pair<ll,ll> cu = solve(mid);
        
        
        if(cu.nd < k)
        {
            rr = mid;
            if(rr == 0)
            {
                return cu.st;
            }
        }
        else if(cu.nd > k)
        {
            l = mid;
            cl = cu;
        }
        else
        {
            //cerr<<cu.st<<"\n";
            return cu.st;
        }
    }
    //cerr<<cl.nd<<" "<<l<<" "<<cl.st<<"\n";
    return cl.st + l * (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)<<"\n";
}*/

컴파일 시 표준 에러 (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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40