Submission #197430

#	Time	Username	Problem	Language	Result	Execution time	Memory
197430		abacaba	Aliens (IOI16_aliens)	C++14	100 / 100	341 ms	136836 KiB

aliens

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int mod = 1e9 + 7;
const ll inf = 2e18;
const int N = 1e5 + 15;
pair <ll, int> dp[N];
int l[N], r[N];
int ord[N];
vector <pii> tmp;
ll val[N];

inline ll sq(ll x) {
    return x * x;
}

inline void Min(pair <ll, int> &a, pair <ll, int> b) {
    a = min(a, b);
}

struct line {
    int k;
    ll b;
    int t;
    line(int k, ll b, int t) : k(k), b(b), t(t) { }
    inline pair <ll, int> get(int x) {
        return mp((ll)k * x + b, t + 1);
    }
};

vector <line> hull;
int ptr;

inline bool bad(line a, line b, line c) {
    if((a.b - c.b) * (c.k - b.k) >= (c.k - a.k) * (b.b - c.b))
        return true;
    if((a.b - c.b) * (c.k - b.k) == (c.k - a.k) * (b.b - c.b) && b.t > c.t)
        return true;
    return false;
}

inline void add(line nw) {
    while(hull.size() > 1 && bad(hull[hull.size() - 2], hull.back(), nw))
        hull.ppb();
    hull.pb(nw);
}

inline pair <ll, int> get(int x) {
    ptr = min(ptr, (int)hull.size() - 1);
    while(ptr + 1 < hull.size() && hull[ptr].get(x) >= hull[ptr + 1].get(x))
        ++ptr;
    return hull[ptr].get(x);
}

inline int check(ll C, int n) {
    hull.clear();
    ptr = 0;
    for(int i = 1; i <= n; ++i) {
        add(*new line(-2 * l[i], sq(l[i]) + dp[i-1].f - val[i], dp[i-1].se));
        pair <ll, int> valnw = get(r[i] + 1);
        valnw.f += sq(r[i] + 1) + C;
        dp[i] = valnw;
    }
    return dp[n].se;
}

ll take_photos(int n, int m, int k, std::vector<int> row, std::vector<int> col) {
    for(int i = 0; i < n; ++i) {
        l[i+1] = min(row[i], col[i]) + 1;
        r[i+1] = max(row[i], col[i]) + 1;
        ord[i+1] = i+1;
    }
    sort(ord + 1, ord + 1 + n, [&](int x, int y) {
        return mp(l[x], -r[x]) < mp(l[y], -r[y]);
    });
    for(int i = 1; i <= n; ++i)
        if(tmp.empty() || !(tmp.back().f <= l[ord[i]] && tmp.back().se >= r[ord[i]]))
            tmp.pb(mp(l[ord[i]], r[ord[i]]));
    n = tmp.size();
    for(int i = 1; i <= n; ++i) {
        l[i] = tmp[i-1].f, r[i] = tmp[i-1].se;
        val[i] = sq(max(0, r[i-1] - l[i] + 1));
    }
    ll l = 0, r = (ll)m * m, res = 0;
    while(l <= r) {
        ll mid = l + r >> 1;
        int val = check(mid, n);
        if(val <= k) {
            r = mid - 1;
            res = mid;
        }
        else
            l = mid + 1;
    }
    check(res, n);
    return (dp[n].f - res * k);
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> get(int)':
aliens.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr + 1 < hull.size() && hull[ptr].get(x) >= hull[ptr + 1].get(x))
           ~~~~~~~~^~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:121:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid = l + r >> 1;
                  ~~^~~

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