Submission #751320

#	Time	Username	Problem	Language	Result	Execution time	Memory
751320		Desh03	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	340 KiB

aliens

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

const long long INF = 1e18;

struct point {
    int x, y;
    bool operator < (const point &p) const {
        return x == p.x ? y < p.y : x < p.x;
    }
};

struct line {
    int m, s;
    long long c;
    line(const int &m_, const long long &c_, const int &s_) : m(m_), c(c_), s(s_), left(NULL), right(NULL) { };
    long long eval(const int &x) {
        return 1LL * m * x + c;
    }
    line *left, *right;
};

int N, M;
vector<point> r;
vector<long long> dp;
vector<int> cnt;

struct lichaotree {
    line* root;
    lichaotree() : root(NULL) { };
    void insert(line* &v, int l, int r, int m_, long long c_, int s_) {
        if (v == NULL || l == r) v = new line(m_, c_, s_);
        if (l == r) return;
        int m = l + r >> 1;
        if (v->eval(m) > 1LL * m_ * m + c_) swap(v->m, m_), swap(v->c, c_), swap(v->s, s_);
        if (v->eval(l) > 1LL * m_ * l + c_) insert(v->left, l, m, m_, c_, s_);
        else insert(v->right, m + 1, r, m_, c_, s_);
    }
    pair<long long, int> qry(line* &v, int l, int r, int x) {
        if (v == NULL) return {INF, INF};
        if (l == r) return {v->eval(x), v->s};
        int m = l + r >> 1;
        if (x <= m) return min({v->eval(x), v->s}, qry(v->left, l, m, x));
        return min({v->eval(x), v->s}, qry(v->right, m + 1, r, x));
    }
    void insert(int m, long long c, int s) {
        insert(root, 0, M, m, c, s);
    }
    pair<long long, int> qry(int x) {
        return qry(root, 0, M, x);
    }
};

long long sq(int x) {
    return 1LL * x * x;
}

void aliens(long long lambda) {
   lichaotree lct;
   lct.insert(-2 * r[0].x, sq(r[0].x) + 1 - 2 * r[0].x, 0);
   for (int i = 0; i < N; i++) {
        auto [mn, cnt_] = lct.qry(r[i].y);
        dp[i] = mn + sq(r[i].y) + 2 * r[i].y - lambda;
        cnt[i] = cnt_ + 1;
        if (i < N - 1) {
            lct.insert(-2 * r[i + 1].x, dp[i] + sq(r[i + 1].x) - 2 * r[i + 1].x + 1 - sq(max(0, r[i].y - r[i + 1].x + 1)), cnt[i]);
        }
   }
}

long long take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
    vector<point> f;
    r = vector<point> (), M = m;
    for (int i = 0; i < n; i++) {
        if (R[i] > C[i]) swap(R[i], C[i]);
        f.push_back({R[i], C[i]});
    }
    sort(f.begin(), f.end());
    r.push_back(f[0]);
    for (int i = 1; i < n; i++) {
        if (r.back().x == f[i].x) {
            r.pop_back();
            r.push_back(f[i]);
        } else if (f[i].y > r.back().y) {
            r.push_back(f[i]);
        }
    }
    N = r.size();
    dp = vector<long long> (N), cnt = vector<int> (N);
    long long l_ = 0, r_ = 1e14;
    while (l_ <= r_) {
        long long m_ = l_ + r_ >> 1;
        aliens(m_);
        if (l_ == r_) break;
        if (cnt[N - 1] > k) l_ = m_ + 1;
        else r_ = m_;
    }
    return dp[N - 1] + l_ * cnt[N - 1];
}

Compilation message (stderr)

aliens.cpp: In constructor 'line::line(const int&, const long long int&, const int&)':
aliens.cpp:16:15: warning: 'line::c' will be initialized after [-Wreorder]
   16 |     long long c;
      |               ^
aliens.cpp:15:12: warning:   'int line::s' [-Wreorder]
   15 |     int m, s;
      |            ^
aliens.cpp:17:5: warning:   when initialized here [-Wreorder]
   17 |     line(const int &m_, const long long &c_, const int &s_) : m(m_), c(c_), s(s_), left(NULL), right(NULL) { };
      |     ^~~~
aliens.cpp: In member function 'void lichaotree::insert(line*&, int, int, int, long long int, int)':
aliens.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int m = l + r >> 1;
      |                 ~~^~~
aliens.cpp: In member function 'std::pair<long long int, int> lichaotree::qry(line*&, int, int, int)':
aliens.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m = l + r >> 1;
      |                 ~~^~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:93:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         long long m_ = l_ + r_ >> 1;
      |                        ~~~^~~~

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