Submission #311846

#	Time	Username	Problem	Language	Result	Execution time	Memory
311846		aZvezda	Aliens (IOI16_aliens)	C++14	4 / 100	3 ms	2304 KiB

aliens

//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e10 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

struct Line {
    ll a, b, delta;
    ll y(ll x) {return x * a + b;}
    Line(ll _a, ll _b, ll _delta) {a = _a; b = _b; delta = _delta;}
    Line() {a = 0; b = mod; delta = 0;}
};
struct Node {
    Line val;
    Node *l, *r;
    Node() {l = nullptr; r = nullptr;}
    ll y(ll x) {return val.y(x);}
    void expand() {
        if(!l) {l = new Node(); r = new Node();}
    }
};
struct LiChao {
    Node root;
    void add(Line nw, Node *curr, ll l = -mod, ll r = mod) {
        if(l == -mod && r == mod) {
            //cout << "Adding " << nw.a << " " << nw.b << " " << nw.delta << endl;
        }
        ll m = (l + r) / 2;
        bool a = nw.y(l) < curr->y(l);
        bool b = nw.y(m) < curr->y(m);
        if(b) {swap(curr->val, nw);}
        if(r - l == 1) {
            return;
        }
        curr->expand();
        if(a != b) {
            add(nw, curr->l, l, m);
        } else {
            add(nw, curr->r, m, r);
        }
    }
    Line get(ll x, Node *curr, ll l = -mod, ll r = mod) {
        if(curr == nullptr) {return Line();}
        ll m = (l + r) / 2;
        if(r - l == 1) {
            return curr->val;
        }
        if(x < m) {
            auto rec = get(x, curr->l, l, m);
            if(curr->y(x) < rec.y(x)) {
                return curr->val;
            } else {
                return rec;
            }
        } else {
            auto rec = get(x, curr->r, l, m);
            if(curr->y(x) < rec.y(x)) {
                return curr->val;
            } else {
                return rec;
            }
        }
    }
    void clear() {
        root = Node();
    }
};

const ll MAX_N = 1e5 + 10;
ll n, m, k;
vector<pair<ll, ll> > points;
ll dp[MAX_N], delta[MAX_N];
LiChao tree;

ll calculate(ll del) {
    tree.clear();
    dp[0] = delta[0] = 0;
    tree.add(Line(-2ll * points[1].second, points[1].second * points[1].second, 0), &(tree.root));
    for(ll i = 1; i < points.size(); i ++) {
        auto best = tree.get(points[i].first, &(tree.root));
        //cout << best.a << " " << best.b << " " << best.delta << " " << best.y(points[i].first) << endl;
        dp[i] = best.y(points[i].first) + points[i].first * points[i].first + del;
        delta[i] = best.delta + 1;
        if(i != points.size() - 1) {
            tree.add(Line(-2ll * points[i + 1].second, dp[i] - max(points[i].first - points[i + 1].second, 0ll) * max(points[i].first - points[i + 1].second, 0ll) + points[i + 1].second * points[i + 1].second, delta[i]), &(tree.root));
        }
        //cout << out(dp[i]) << out(delta[i]) << endl;
    }
    return delta[points.size() - 1];
}


long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) {
    n = N; m = M; k = K;
    for(ll i = 0; i < n; i ++) {
        if(r[i] < c[i]) {
            points.push_back({c[i], -r[i]});
        } else {
            points.push_back({r[i], -c[i]});
        }
    }
    sort(points.begin(), points.end());
    vector<pair<ll, ll> > cpy;
    ll mn = mod;
    for(ll i = n - 1; i >= 0; i --) {
        if(-points[i].second < mn) {
            mn = -points[i].second;
            cpy.push_back({points[i].first + 1, -points[i].second});
        }
    }
    cpy.push_back({0, 0});
    points = cpy;
    reverse(points.begin(), points.end());
    for(auto it : points) {
        //cout << it << endl;
    }
    ll lft = -mod, rght = mod;

    while(lft < rght - 1) {
        ll m = (lft + rght) / 2ll;
        if(calculate(m) >= k) {
            lft = m;
        } else {
            rght = m;
        }
        //cout << out(lft) << out(m) << out(rght) << endl << endl;
    }
    calculate(lft);
    return dp[cpy.size() - 1] - min(k, delta[cpy.size() - 1]) * lft;
}

Compilation message (stderr)

aliens.cpp: In function 'll calculate(ll)':
aliens.cpp:87:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(ll i = 1; i < points.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~~
aliens.cpp:92:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if(i != points.size() - 1) {
      |            ~~^~~~~~~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:122:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
  122 |     for(auto it : points) {
      |              ^~

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