Submission #1275550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275550		afonsopereira	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	348 KiB

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

typedef long long ll;

class LinearFunction {
private:
    ll slope, intercept;
    
public:
    LinearFunction(ll m, ll c) : slope(m), intercept(c) {}
    
    ll evaluate(ll x) const {
        return slope * x + intercept;
    }
    
    ll getSlope() const { return slope; }
    ll getIntercept() const { return intercept; }
};

class ConvexHullTrick {
private:
    deque<LinearFunction> hull;

    bool isRedundant(const LinearFunction& left, const LinearFunction& mid, const LinearFunction& right) {
        __int128 lhs = (__int128)(left.getSlope() - right.getSlope()) * 
                       (__int128)(mid.getIntercept() - left.getIntercept());
        __int128 rhs = (__int128)(left.getSlope() - mid.getSlope()) * 
                       (__int128)(right.getIntercept() - left.getIntercept());
        return lhs <= rhs;
    }
    
public:
    void insert(LinearFunction func) {
        if (!hull.empty() && hull.front().getSlope() == func.getSlope()) {
            if (hull.front().getIntercept() <= func.getIntercept()) {
                return;
            }
            hull.pop_front();
        }

        while (hull.size() >= 2) {
            if (isRedundant(func, hull[0], hull[1])) {
                hull.pop_front();
            } else {
                break;
            }
        }
        
        hull.push_front(func);
    }
    
    ll queryMin(ll x) {
        while (hull.size() >= 2) {
            int lastIdx = hull.size() - 1;
            if (hull[lastIdx].evaluate(x) >= hull[lastIdx - 1].evaluate(x)) {
                hull.pop_back();
            } else {
                break;
            }
        }
        
        return hull.back().evaluate(x);
    }
};

struct Segment {
    int start, end;
    
    Segment(int s, int e) : start(s), end(e) {}
    
    bool operator<(const Segment& other) const {
        if (start != other.start) return start < other.start;
        return end > other.end;
    }
    
    ll coverage() const {
        return (ll)(end - start + 1) * (end - start + 1);
    }
};

vector<Segment> preprocessSegments(int n, vector<int>& r, vector<int>& c) {
    vector<Segment> segments;
    segments.reserve(n);
    
    for (int i = 0; i < n; i++) {
        int startPos = min(r[i], c[i]);
        int endPos = max(r[i], c[i]);
        segments.emplace_back(startPos, endPos);
    }
    
    sort(segments.begin(), segments.end());

    vector<Segment> filtered;
    int maxEnd = -1;
    
    for (const auto& seg : segments) {
        if (seg.end > maxEnd) {
            filtered.push_back(seg);
            maxEnd = seg.end;
        }
    }
    
    return filtered;
}

ll calculateOverlap(const Segment& prev, const Segment& curr) {
    if (curr.start > prev.end) return 0;
    ll overlap = prev.end - curr.start + 1;
    return overlap * overlap;
}

pair<ll, int> solveWithPenalty(const vector<Segment>& segments, ll penalty) {
    int n = segments.size();
    vector<ll> dp(n + 1, 1e18);
    vector<int> count(n + 1, 0);
    
    dp[0] = 0;
    ConvexHullTrick cht;
    
    for (int i = 0; i <= n; i++) {
        if (i > 0) {
            ll x = segments[i - 1].end;
            ll minCost = cht.queryMin(x);
            dp[i] = minCost + x * x + penalty;
        }
        
        if (i < n) {
            ll slope = -2 * segments[i].start + 2;
            ll overlap = (i > 0) ? calculateOverlap(segments[i - 1], segments[i]) : 0;
            ll base = segments[i].start - 1;
            ll intercept = dp[i] + base * base - overlap;
            
            cht.insert(LinearFunction(slope, intercept));
        }
    }
    
    // calculate number of segments used
    count[n] = 0;
    vector<ll> tempDp = dp;
    for (int i = n - 1; i >= 0; i--) {
        ll x = segments[i].end;
        ll costWithSegment = segments[i].coverage();
        if (i > 0) {
            costWithSegment -= calculateOverlap(segments[i - 1], segments[i]);
        }
        
        for (int j = i + 1; j <= n; j++) {
            if (dp[j] - dp[i] - penalty <= costWithSegment + 1e-9) {
                count[i] = count[j] + 1;
                break;
            }
        }
    }
    
    return {dp[n], count[0]};
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    auto segments = preprocessSegments(n, r, c);
    n = segments.size();
    
    if (n <= k) {
        // can use one segment per point
        ll total = 0;
        for (int i = 0; i < n; i++) {
            total += segments[i].coverage();
            if (i > 0) {
                total -= calculateOverlap(segments[i - 1], segments[i]);
            }
        }
        return total;
    }

    ll left = 0, right = (ll)m * m;
    
    while (right - left > 2) {
        ll mid1 = left + (right - left) / 3;
        ll mid2 = right - (right - left) / 3;
        
        ll cost1 = solveWithPenalty(segments, mid1).first;
        ll cost2 = solveWithPenalty(segments, mid2).first;
        
        if (cost1 > cost2) {
            left = mid1;
        } else {
            right = mid2;
        }
    }
    
    ll result = 1e18;
    for (ll penalty = left; penalty <= right; penalty++) {
        auto [cost, numSegments] = solveWithPenalty(segments, penalty);
        if (numSegments <= k) {
            result = min(result, cost + (k - numSegments) * penalty);
        }
    }
    
    return result;
}

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
      |         ^~~~

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