Submission #522420

#	Time	Username	Problem	Language	Result	Execution time	Memory
522420		lohacho	Aliens (IOI16_aliens)	C++14	25 / 100	6 ms	5128 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

const long long NS = (long long)2e5 + 4;
long long n;
vector<long long> line[NS];
long long f, r;

long long cross(vector<long long> x, vector<long long> y){
    long long val = (x[1] - y[1]) / (y[0] - x[0]);
    return val + (val >= 0 && (x[1] - y[1]) % (y[0] - x[0]) ? 1 : 0);
}

void push(long long a, long long b, long long c){
    while(f + 1 < r && cross({a, b}, line[r - 1]) <= cross(line[r - 1], line[r - 2])) --r;
    line[r++] = {a, b, c};
}

pair<long long, long long> get(long long x){
    while(f + 1 < r && line[f][0] * x + line[f][1] >= line[f + 1][0] * x + line[f + 1][1]) ++f;
    return {line[f][0] * x + line[f][1], line[f][2]};
}

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
    vector<pair<long long, long long>> a(n);
    for(long long i = 0; i < n; ++i){
        a[i].first = R[i], a[i].second = C[i];
        if(a[i].first > a[i].second){
            swap(a[i].first, a[i].second);
        }
    }
    sort(a.begin(), a.end());
    vector<pair<long long, long long>> stk = {a[0]};
    for(long long i = 1; i < n; ++i){
        if(stk.back().first == a[i].first) ma(stk.back().second, a[i].second);
        else if(stk.back().second < a[i].second) stk.push_back(a[i]);
    }
    a = stk; n = (long long)a.size();
    long long low = (long long)-1e13, high = (long long)1e13;
    auto sol = [&](long long pl)->pair<long long, long long>{
        f = r = 0;
        vector<pair<long long, long long>> dp(n);
        push(-(a[0].first - 1) * 2 * 2, (a[0].first - 1) * (a[0].first - 1) * 2, 0);
        for(long long i = 0; i < n; ++i){
            auto rv = get(a[i].second);
            dp[i] = {rv.first + a[i].second * a[i].second * 2 + pl, rv.second + 1};
            auto nsame = 0;
            if(i + 1 < n && a[i + 1].first <= a[i].second){
                nsame = (a[i].second - a[i + 1].first + 1) * (a[i].second - a[i + 1].first + 1);
            }
            if(i + 1 < n) push(-(a[i + 1].first - 1) * 2 * 2, ((a[i + 1].first - 1) * (a[i + 1].first - 1) - nsame) * 2 + dp[i].first, dp[i].second);
        }
        return dp[n - 1];
    };
    mi(k, n);
    while(low < high){
        long long mid = low + high >> 1;
        auto rv = sol(mid * 2 + 1);
        //cout << low << ' ' << high << ' ' << mid << ' ' << rv.first << ' ' << rv.second << endl;
        if(rv.second <= k){
            high = mid;
        }
        else{
            low = mid + 1;
        }
    }
    low = low * 2;
    auto rv = sol(low);
    //cout << rv.first << ' ' << rv.second << ' ' << low << endl;
    return ((rv.first - k * low) >> 1);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:60:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         long long mid = low + high >> 1;
      |                         ~~~~^~~~~~

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