Submission #158028

#	Time	Username	Problem	Language	Result	Execution time	Memory
158028		johutha	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	380 KiB

aliens

#include "aliens.h"
#include <vector>
#include <iostream>
#include <deque>
#include <algorithm>

#define int long long

using namespace std;

struct solver
{
    vector<int> l;
    vector<int> r;
    int k;
    int n;
    int m;
    vector<int> overlap;

    pair<int,int> run(int c)
    {
        deque<pair<int,int>> q;
        vector<int> ks(n + 1, 0);
        vector<int> dp(n + 1, 0);
        int ck = 0;
        for (int i = 1; i <= n; i++)
        {
            int a = -2*l[i - 1];
            int b = dp[i - 1] - 2*l[i - 1] + l[i - 1]*l[i - 1] - overlap[i - 1];
            q.push_back({a, b});
            int rv = r[i - 1];
            while (q.size() > 1)
            {
                int v0 = q[0].first * rv + q[0].second;
                int v1 = q[1].first * rv + q[1].second;
                if (v1 < v0)
                {
                    ck++;
                    q.pop_front();
                }
                else
                {
                    break;
                }
            }
            ks[i] = ks[ck] + 1;
            dp[i] = q[0].first * rv + q.front().second + c + r[i - 1]*r[i - 1] + 2*r[i - 1] + 1;
        }
        return {ks[n], dp[n]};
    }

    int solve()
    {
        overlap.resize(n, 0);
        for (int i = 1; i < n; i++)
        {
            if (r[i - 1] >= l[i])
            {
                overlap[i] = (r[i - 1] - l[i] + 1)*(r[i - 1] - l[i] + 1);
            }
        }

        int bl = 0;
        int br = m*m;
        while (br - bl > 1)
        {
            int m = (bl + br)/2;
            if (run(m).first < k)
            {
                br = m;
            }
            else
            {
                bl = m;
            }
        }
        auto fin = run(bl);
        return fin.second - bl*fin.first;
    }
};

int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
    vector<pair<int,int>> intervals;
    for (int i = 0; i < n; i++)
    {
        intervals.push_back({min(r[i], c[i]), -max(r[i], c[i])});
    }
    sort(intervals.begin(), intervals.end());
    vector<int> nl;
    vector<int> nr;
    int mmx = -1;
    for (int i = 0; i < n; i++)
    {
        if (-intervals[i].second > mmx)
        {
            nl.push_back(intervals[i].first);
            nr.push_back(-intervals[i].second);
            mmx = -intervals[i].second;
        }
    }
    int nn = nl.size();
    solver s;
    s.l = nl;
    s.r = nr;
    s.k = k;
    s.n = nn;
    s.m = m;
    return s.solve();
}

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