oj.uz

Submission #158090

# Submission time Handle Problem Language Result Execution time Memory
158090 2019-10-14T17:52:52 Z johutha Aliens (IOI16_aliens) C++14
0 / 100
 2 ms 508 KB 
#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 fl = run(bl);
        auto fr = run(br);
        int v1 = fl.second - fl.first * bl;
        int v2 = fr.second - fr.first * br;
        int diff = v2 - v1;
        int kdf = fl.first - fr.first;
        return v1 + (diff/kdf)*(fl.first - k);
    }
};

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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 508 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 8 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -