제출 #1118894

#제출 시각아이디문제언어결과실행 시간메모리
1118894vjudge1Aliens (IOI16_aliens)C++17
25 / 100
45 ms14820 KiB
// #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") // #define _GLIBCXX_DEBUG // #define _GLIBCXX_DEBUG_PEDANTIC #ifdef LOCAL #else #include "aliens.h" #endif #include <iomanip> #include <cassert> #include <iostream> #include <vector> #include <random> #include <algorithm> #include <map> #include <set> #include <functional> #include <array> #include <numeric> #include <queue> #include <deque> #include <bitset> #include <cmath> #include <climits> #include <cstdint> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> // using namespace __gnu_pbds; // using namespace __gnu_cxx; using namespace std; const int MOD = 998244353; const long double PI = 3.141592653589793; using ll = long long; const ll INF = 1e18; // #define int ll // --------> sashko123`s defines: #define itn int //Vasya sorry :( #define p_b push_back #define fi first #define se second #define pii std::pair<int, int> #define oo LLONG_MAX #define big INT_MAX #define elif else if int input() { int x; cin >> x; return x; } // ----------> end of sashko123`s defines (thank you Vasya <3) // template<typename K, typename V> // using hash_table = cc_hash_table<K, V, hash<K>>; // template<typename T> // using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; template<typename T> struct li_chao_tree { const T MX = 1e9 + 1; struct line { T k = 0; T b = -INF; ll lam = 0; pair<T, T> f(T x) const { return {k * x + b, lam}; } }; struct node { line ln; int id = 0; node* left = nullptr; node* right = nullptr; }; node* new_node() { const int N = 100000; static node* block; static int count = N; if (count == N) { block= new node[N]; count = 0; } return (block + count++); }; node* root = new_node(); pair<T,T> get(T x) { auto [y, lam] = get(root, -MX, MX, x); return {-y, -lam}; } void add(line ln) { ln.b *= -1; ln.k *= -1; ln.lam *= -1; add(root, -MX, MX, ln); } pair<T,T> get(node*& v, T l, T r, T x) { if (!v || l > r) { return {-INF, -INF}; } auto ans = v->ln.f(x); if (r == l) { return ans; } T mid = (r + l) / 2; if (x <= mid) { return max(ans, get(v->left, l, mid, x)); } else { return max(ans, get(v->right, mid + 1, r, x)); } } void add(node*& v, T l, T r, line ln) { if (l > r) return; if (!v) { v = new_node(); } T m = (r + l) / 2; bool left = v->ln.f(l) < ln.f(l); bool md = v->ln.f(m) < ln.f(m); if (md) swap(v->ln, ln); if (l == r) { return; } if (left != md) { add(v->left, l, m, ln); } else { add(v->right, m + 1, r, ln); } } }; vector<pii> a; const int N = 600; const int K = 600; ll W(ll l, ll r) { if (r - l >= 0) return (r - l) * (r - l); return 0ll; } vector<pii> recalc(vector<pii> a, int n) { sort(a.begin(), a.end(), [&](pii x, pii y) { return tuple{x.second, -x.first} < tuple{y.second, -y.first}; }); set<pii> st; for (int i = 0; i < n; i++) { auto [l, r] = a[i]; while (!st.empty() && st.rbegin()->first >= l) { st.erase(prev(st.end())); } st.insert({l, r}); } return vector(st.begin(), st.end()); } pair<ll, ll> check(int n, ll lambda) { li_chao_tree<ll> ch; ch.add({.k = -2 * a[1].first, .b = 1ll * a[1].first * a[1].first, .lam = 0}); ll cur = 0, cnt = 0; for (int i = 1; i <= n; i++) { auto best = ch.get(a[i].second); cur = best.first + 1ll * a[i].second * a[i].second + lambda; cnt = best.second + 1; if (i + 1 <= n) { ll k = -2 * a[i + 1].first; ll b = cur - W(a[i + 1].first, a[i].second) + 1ll * a[i + 1].first * a[i + 1].first; ch.add({k, b, cnt}); } } return {cur, cnt}; } ll take_photos(int n, int m, int k, vector<int> rr, vector<int> cc) { a.resize(n); for (int i = 0; i < n; i++) { int r = rr[i], c = cc[i]; if (r > c) swap(r, c); a[i] = {r, c}; } a = recalc(a, n); n = a.size(); for (int i = 0; i < n; i++) a[i].first--; a.insert(a.begin(), {0, 0}); if (check(n, 0).second <= k) { auto [res, cnt] = check(n, 0); return res; } ll l = 0, r = 1e9; while (r - l > 1) { auto mid = (r + l) / 2; if (check(n, mid).second <= k) r = mid; else l = mid; } auto [res, cnt] = check(n, r); return res - r * k; } #ifdef LOCAL int32_t main(int32_t argc, const char * argv[]) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); // insert code here... int n, m, k; cin >> n >> m >> k; vector<int> rr(n); vector<int> cc(n); for (int i = 0; i < n; i++) cin >> rr[i] >> cc[i]; cout << take_photos(n, m, k, rr, cc); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...