Submission #1019228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019228		Thanhs	Aliens (IOI16_aliens)	C++14	0 / 100	5 ms	448 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 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 + C[1].fi * C[1].fi}, 0);
    for (int i = 1; i <= n; i++)
    {
        pair<int,int> res = query(C[i].se);
        res.fi += C[i].se * 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 + C[i + 1].fi * C[i + 1].fi - max(C[i].fi - C[i + 1].fi + 1, 0ll) * 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 = 1e18 + 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);
    return res.fi - res.se * r;
}

// signed main()
// {
//     fastIO
//     freopen("in.txt","r",stdin);
//     freopen("out.txt","w",stdout);
//     cin >> n >> m >> k;
//     for (int i = 1; i <= n; i++) {
//         cin >> C[i].fi >> C[i].se;
//         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 = n * n + 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);
//     cout << res.fi - res.se * r;
// }

Compilation message (stderr)

aliens.cpp: In function 'void upd(line, long long int, node*, long long int, long long int)':
aliens.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     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:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int m = l + r >> 1;
      |             ~~^~~
aliens.cpp:72:17: warning: statement has no effect [-Wunused-value]
   72 |     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:137:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         int m = l + r >> 1;
      |                 ~~^~~
aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
aliens.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

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