Submission #1206857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206857		catling	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    using namespace std;
    typedef long long ll;
    const ll INF = 1e18;

    int N = n;
    vector<pair<int,int>> pointsArray(N);
    for (int i = 0; i < N; i++) {
        int A = min(r[i], c[i]);
        int B = max(r[i], c[i]);
        pointsArray[i] = {A, B};
    }
    sort(pointsArray.begin(), pointsArray.end());

    vector<ll> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) {
        A[i] = pointsArray[i - 1].first;
        B[i] = pointsArray[i - 1].second;
    }

    vector<ll> segmentTree(4 * (N + 1), -INF);
    function<void(int, int, int)> buildTree = [&](int idx, int L, int R) {
        if (L == R) {
            segmentTree[idx] = B[L];
        } else {
            int M = (L + R) / 2;
            buildTree(2 * idx, L, M);
            buildTree(2 * idx + 1, M + 1, R);
            segmentTree[idx] = max(segmentTree[2 * idx], segmentTree[2 * idx + 1]);
        }
    };
    buildTree(1, 1, N);

    function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
        if (r < L || R < l) return -INF;
        if (l <= L && R <= r) return segmentTree[idx];
        int M = (L + R) / 2;
        return max(queryMax(2 * idx, L, M, l, r), queryMax(2 * idx + 1, M + 1, R, l, r));
    };

    vector<ll> valueDP(N + 1);
    vector<int> segmentsDP(N + 1);
    ll lambdaPenalty;

    function<void(int, int, int, int)> divideSolve = [&](int L, int R, int optL, int optR) {
        if (L > R) return;
        int mid = (L + R) / 2;
        ll bestVal = INF;
        int bestK = -1, bestSeg = 0;
        int ub = min(optR, mid - 1);
        for (int j = optL; j <= ub; ++j) {
            ll maxVal = queryMax(1, 1, N, j + 1, mid);
            ll len = maxVal - A[j + 1] + 1;
            ll cost = len * len + lambdaPenalty;
            ll candidate = valueDP[j] + cost;
            int segs = segmentsDP[j] + 1;
            if (candidate < bestVal || (candidate == bestVal && segs < bestSeg)) {
                bestVal = candidate;
                bestSeg = segs;
                bestK = j;
            }
        }
        valueDP[mid] = bestVal;
        segmentsDP[mid] = bestSeg;
        divideSolve(L, mid - 1, optL, bestK);
        divideSolve(mid + 1, R, bestK, optR);
    };

    auto runLambda = [&](ll lam) -> pair<ll, int> {
        lambdaPenalty = lam;
        fill(valueDP.begin(), valueDP.end(), INF);
        fill(segmentsDP.begin(), segmentsDP.end(), 0);
        valueDP[0] = 0;
        divideSolve(1, N, 0, N - 1);
        return {valueDP[N], segmentsDP[N]};
    };

    ll L = 0, R = 4LL * m * m + 10;
    while (L < R) {
        ll mid = (L + R) / 2;
        auto [cost, segs] = runLambda(mid);
        if (segs > k) {
            L = mid + 1;
        } else {
            R = mid;
        }
    }

    auto [finalVal, usedSegments] = runLambda(L);
    return finalVal - L * usedSegments;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:24:5: error: 'function' was not declared in this scope
   24 |     function<void(int, int, int)> buildTree = [&](int idx, int L, int R) {
      |     ^~~~~~~~
aliens.cpp:2:1: note: 'std::function' is defined in header '<functional>'; did you forget to '#include <functional>'?
    1 | #include "aliens.h"
  +++ |+#include <functional>
    2 | 
aliens.cpp:24:32: error: expression list treated as compound expression in functional cast [-fpermissive]
   24 |     function<void(int, int, int)> buildTree = [&](int idx, int L, int R) {
      |                                ^
aliens.cpp:24:14: error: expected primary-expression before 'void'
   24 |     function<void(int, int, int)> buildTree = [&](int idx, int L, int R) {
      |              ^~~~
aliens.cpp:34:5: error: 'buildTree' was not declared in this scope
   34 |     buildTree(1, 1, N);
      |     ^~~~~~~~~
aliens.cpp:36:40: error: expression list treated as compound expression in functional cast [-fpermissive]
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                                        ^
aliens.cpp:36:16: error: expected primary-expression before '(' token
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                ^
aliens.cpp:36:17: error: expected primary-expression before 'int'
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                 ^~~
aliens.cpp:36:22: error: expected primary-expression before 'int'
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                      ^~~
aliens.cpp:36:27: error: expected primary-expression before 'int'
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                           ^~~
aliens.cpp:36:32: error: expected primary-expression before 'int'
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                                ^~~
aliens.cpp:36:37: error: expected primary-expression before 'int'
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                                     ^~~
aliens.cpp:36:43: error: 'queryMax' was not declared in this scope
   36 |     function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
      |                                           ^~~~~~~~
aliens.cpp:47:37: error: expression list treated as compound expression in functional cast [-fpermissive]
   47 |     function<void(int, int, int, int)> divideSolve = [&](int L, int R, int optL, int optR) {
      |                                     ^
aliens.cpp:47:14: error: expected primary-expression before 'void'
   47 |     function<void(int, int, int, int)> divideSolve = [&](int L, int R, int optL, int optR) {
      |              ^~~~
aliens.cpp: In lambda function:
aliens.cpp:76:9: error: 'divideSolve' was not declared in this scope
   76 |         divideSolve(1, N, 0, N - 1);
      |         ^~~~~~~~~~~
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
      |         ^~~~