Submission #1206841

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

aliens

// Catling
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second <<')';}
auto operator<<(auto&o,auto X)->decltype(X.end(),o){o<<'{';int i=2;for(auto e:X)o<<(", ")+i<<e,i=0;return o<<'}';}
#define LOG(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define LOG(X...)(void)0
#endif

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#define all(X)  (X).begin(),(X).end()
#define endl    '\n'
#define size(X)  X.size()

const ll INF = 9223372036854775806 / 4;
const ll MAX_N = 1e9+1;
const ll MOD = 1e9+7; // 998244353

int N, M, K;
vector<pair<int,int>> pointsArray;
vector<ll> A, B;

vector<ll> segmentTree;
void buildTree(int indexValue, int l, int R) {
    if (l == R) {
        segmentTree[indexValue] = B[l];
    } else {
        int middleIndex = (l + R) / 2;
        buildTree(indexValue * 2, l, middleIndex);
        buildTree(indexValue * 2 + 1, middleIndex + 1, R);
        segmentTree[indexValue] = max(segmentTree[indexValue * 2], segmentTree[indexValue * 2 + 1]);
    }
}
ll queryMax(int indexValue, int l, int R, int secondL, int secondR) {
    if (secondR < l || R < secondL) return -INF;
    if (secondL <= l && R <= secondR) return segmentTree[indexValue];
    int middleIndex = (l + R) / 2;
    return max(
        queryMax(indexValue * 2, l, middleIndex, secondL, secondR),
        queryMax(indexValue  * 2 + 1, middleIndex + 1, R, secondL, secondR)
    );
}

vector<ll> valueDP;
vector<int> segmentsDP;
ll lambdaPenalty;

void divideSolve(int L, int R, int optimalL, int optimalR) {
    if (L > R) return;
    int middleIndex = (L + R) / 2;
    ll bestValue = INF;
    int bestK = -1, bestSegment = 0;
    int upperBound = min(optimalR, middleIndex - 1);
    for (int j = optimalL; j <= upperBound; j++) {
        ll maxValue = queryMax(1, 1, N, j + 1, middleIndex);
        ll currentLength = maxValue - A[j + 1] + 1;
        ll currentCost = currentLength * currentLength + lambdaPenalty;
        ll candidateScore = valueDP[j] + currentCost;
        int segmentsCounter = segmentsDP[j] + 1;
        if (candidateScore < bestValue || (candidateScore == bestValue && segmentsCounter < bestSegment)) {
            bestValue = candidateScore;
            bestSegment = segmentsCounter;
            bestK = j;
        }
    }
    valueDP[middleIndex] = bestValue;
    segmentsDP[middleIndex] = bestSegment;
    divideSolve(L, middleIndex - 1, optimalL, bestK);
    divideSolve(middleIndex + 1, R, bestK, optimalR);
}

pair<ll,int> runLambda(ll lam) {
    lambdaPenalty = lam;
    valueDP.assign(N + 1, INF);
    segmentsDP.assign(N + 1, 0);
    valueDP[0] = 0;
    segmentsDP[0] = 0;
    divideSolve(1, N, 0, N - 1);
    return {valueDP[N], segmentsDP[N]};
}

void solveTestCase() {
    cin >> N >> M >> K;
    pointsArray.resize(N);
    
    for (int i = 0; i < N; i++) {
        int R, C;
        cin >> R >> C;
        int A = min(R, C);
        int B = max(R, C);
        pointsArray[i] = {A, B};
    }
    sort(pointsArray.begin(), pointsArray.end());
    A.assign(N + 1, 0);
    B.assign(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        A[i] = pointsArray[i - 1].first;
        B[i] = pointsArray[i - 1].second;
    }

    segmentTree.assign(4 * (N + 1), -INF);
    buildTree(1, 1, N);

    ll leftBound = 0, rightBound = (ll)2 * M * (ll)2 * M + 5;
    while (leftBound < rightBound) {
        ll middleIndex = leftBound + (rightBound - leftBound)/2;
        auto [F, argumentMax] = runLambda(middleIndex);
        if (argumentMax > K) leftBound = middleIndex + 1;
        else rightBound = middleIndex;
    }
    auto [optimalValue, optimalCount] = runLambda(leftBound);
    ll finalAnswer = optimalValue - leftBound * (ll) optimalCount;
    cout << finalAnswer << endl;
    return;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int T = 1;

    while(T--) {
        solveTestCase();
    }
    return 0;
}

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
      |         ^~~~
/usr/bin/ld: /tmp/ccXC4DaI.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccp3UomU.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccXC4DaI.o: in function `main':
grader.cpp:(.text.startup+0xff): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status