Submission #522565

#	Time	Username	Problem	Language	Result	Execution time	Memory
522565		pokmui9909	Aliens (IOI16_aliens)	C++17	100 / 100	191 ms	7772 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
  
#define x first
#define y second
ll N, M, K;
pair<ll, ll> A[100005];
ll L[100005];
ll R[100005];
pair<ll, ll> D[100005];
void init(){
    sort(A + 1, A + N + 1, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool{
        if(a.y != b.y) return a.y < b.y;
        else return a.x > b.x;
    });
    vector<pair<ll, ll>> B;
    for(int i = 1; i <= N; i++){
        while(B.size() && B.back().x >= A[i].x) B.pop_back();
        B.push_back(A[i]);
    }
    for(int i = 0; i < B.size(); i++){
        L[i + 1] = B[i].x, R[i + 1] = B[i].y;
    }
    N = B.size();
}
struct Line{
    ll a, b, i;
    ll f(ll x){
        return a * x + b;
    }
};
lf X_cross(Line f, Line g){
    return 1.0 * (f.b - g.b) / (g.a - f.a);
}
ll f(ll v){
    deque<Line> dq;
    dq.push_back({-4 * L[1], 2 * L[1] * L[1], 0});
    for(int i = 1; i <= N; i++){
        while(dq.size() >= 2 && dq[0].f(R[i] + 1) >= dq[1].f(R[i] + 1)) dq.pop_front();
        D[i].x = dq[0].f(R[i] + 1) + (R[i] + 1) * (R[i] + 1) * 2 + v;
        D[i].y = dq[0].i + 1;
        Line f = {-4 * L[i + 1], D[i].x - max(0LL,R[i]-L[i+1]+1)*max(0LL,R[i]-L[i+1]+1)*2 + L[i+1]*L[i+1]*2, D[i].y};
        while(dq.size() >= 2 && X_cross(f, dq[dq.size() - 2]) >= X_cross(f, dq[dq.size() - 1])) dq.pop_back();
        dq.push_back(f);
    }
    return D[N].y;
}
  
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {;
   	N = n, M = m, K = k;
    K = min(K, N);
    for(int i = 1; i <= N; i++){
      	A[i] = {r[i - 1], c[i - 1]};
        A[i].x++; A[i].y++;
        if(A[i].x > A[i].y){
            swap(A[i].x, A[i].y);
        }
    }
    init();
    ll S = 0, E = 2e12 + 7;
    while(S <= E){
        ll m = (S + E) / 2;
        if(f(m * 2 + 1) <= K) E = m - 1;
        else S = m + 1;
    }
    f(S * 2);	
    return D[N].x / 2 - S * K;
}

Compilation message (stderr)

aliens.cpp: In function 'void init()':
aliens.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < B.size(); i++){
      |                    ~~^~~~~~~~~~

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