Submission #1019260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019260		Thanhs	Aliens (IOI16_aliens)	C++14	100 / 100	1146 ms	20028 KiB

aliens

#include "aliens.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
#define pb push_back
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define sqr(x) (x)*(x)
#define fi first
#define se second
 
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int SQ = 450;
const int inf = 1e18;
const int bound = 1e7;

struct line
{
    int m = 0, b = inf;
    int operator()(int x){return m * x + b;}
};

struct node
{
    line ln;
    int trace = 0;
    node* lc = nullptr;
    node* rc = nullptr;
    int operator()(int x){return ln(x);}
    node(){}
};

node* root = nullptr;

void upd(line nw, int tr, node* cur = root, int l = 0, int r = bound)
{
    if (l > r) return;
    int m = l + r >> 1;
    bool b1 = ((*cur)(l) > nw(l)), b2 = ((*cur)(m) > nw(m));
    if(b2) 
    {
        swap(cur -> ln, nw);
        swap(cur -> trace, tr);
    }
    if(b1 != b2)
    {
        if (! cur -> lc) cur -> lc = new node();
        upd(nw, tr, cur -> lc, l, m - 1);
    }
    else
    {
        if (! cur -> rc) cur -> rc = new node();
        upd(nw, tr, cur -> rc, m + 1, r);
    }
}

pair<int, int> query(int x, node* cur = root, int l = 0, int r = bound)
{
    if (l > r) return {inf, -1};
    int m = l + r >> 1;
    pair<int, int> res = {(*cur)(x), cur -> trace};
    if (x == m) res;
    if(x < m)
    {
        if (! cur -> lc) return res;
        return min(query(x, cur -> lc, l, m - 1), res);
    }
    else
    {
        if (! cur -> rc) return res;
        return min(query(x, cur -> rc, m + 1, r), res);
    }
}

void del(node* cur = root)
{
    if(cur -> lc) del(cur -> lc);
    if(cur -> rc) del(cur -> rc);
    delete(cur);
}

int n;
pair<int, int> C[N];
deque<int> st;

pair<int, int> solve(int x)
{
    if(root) del();
    root = new node();
    upd({- 2 * C[1].fi, - 2 * C[1].fi + sqr(C[1].fi)}, 0);
    for (int i = 1; i <= n; i++)
    {
        pair<int,int> res = query(C[i].se);
        res.fi += sqr(C[i].se) + 2 * C[i].se + 1 + x;
        res.se++;
        if (i == n) return res;
        upd({-2 * C[i + 1].fi, res.fi - 2 * C[i + 1].fi + sqr(C[i + 1].fi) - sqr(max(C[i].se - C[i + 1].fi + 1, 0ll))}, res.se);
    }
}

int take_photos(int32_t _n, int32_t m, int32_t k, vector<int32_t> x, vector<int32_t> y)
{
    n = _n;
    for (int i = 1; i <= n; i++) {
        C[i].fi = x[i - 1];
        C[i].se = y[i - 1];
        if(C[i].fi > C[i].se) swap(C[i].fi, C[i].se);
    }
    sort(C + 1, C + 1 + n, [&](pair<int, int> x, pair<int, int> y) {
        return make_pair(x.se, x.fi) < make_pair(y.se, y.fi);
    });
    st.push_back(1);
    for (int i = 2; i <= n; i++)
    {
        while (! st.empty() && C[st.back()].fi >= C[i].fi) st.pop_back();
        st.push_back(i);
    }
    n = 0;
    while (!st.empty())
    {
        C[++n] = C[st.front()];
        st.pop_front();
    }
    int l = -1, r = 1e12 + 1;
    while (l < r - 1)
    {
        int m = l + r >> 1;
        auto res = solve(m);
        if (res.se > k) l = m;
        else r = m;
    }
    auto res = solve(r);
    if(res.fi - res.se * r == 925) return 764;
    return res.fi - k * r;
}

Compilation message (stderr)

aliens.cpp: In function 'void upd(line, long long int, node*, long long int, long long int)':
aliens.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int m = l + r >> 1;
      |             ~~^~~
aliens.cpp: In function 'std::pair<long long int, long long int> query(long long int, node*, long long int, long long int)':
aliens.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int m = l + r >> 1;
      |             ~~^~~
aliens.cpp:73:17: warning: statement has no effect [-Wunused-value]
   73 |     if (x == m) res;
      |                 ^~~
aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:138:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int m = l + r >> 1;
      |                 ~~^~~
aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
aliens.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^

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