제출 #1118865

#제출 시각아이디문제언어결과실행 시간메모리
1118865vjudge1Aliens (IOI16_aliens)C++17
컴파일 에러
0 ms0 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 #include "aliens.h" #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; T f(T x) const { return k * x + b; } }; struct node { line ln; 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(); T get(T x) { return -get(root, -MX, MX, x); } void add(line ln) { ln.b *= -1; ln.k *= -1; add(root, -MX, MX, ln); } T get(node*& v, T l, T r, T x) { if (!v || l > r) { return -INF; } T 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 dp[N][K]; ll W(ll l, ll r) { return max(0ll, (r - l) * (r - l)); } 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()); } ll solve(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}); // cerr << a.size() << "\n"; dp[0][0] = 0; for (int c = 1; c <= k; c++) { li_chao_tree<ll> ch; ch.add({.k = -2 * a[1].first, .b = dp[0][c - 1] + a[1].first * a[1].first}); for (int i = 1; i <= n; i++) { dp[i][c] = ch.get(a[i].second) + a[i].second * a[i].second; if (i + 1 <= n) { ll k = -2 * a[i + 1].first; ll b = dp[i][c - 1] - W(a[i + 1].first, a[i].second) + a[i + 1].first * a[i + 1].first; ch.add({k, b}); } } } return dp[n][k]; } // 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 tt= 1; // // std::cin >> tt; // for (int t = 1; t <= tt; t++) { // // cout << "Case #" << t << ": "; // solve(); // } // return 0; // }

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccNSJDEj.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status