# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
790123 | WLZ | Aliens (IOI16_aliens) | C++17 | 컴파일 에러 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG#include "../../../debug.h"
#else
#define debug(...) 0
#endif
using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp:4:13: warning: extra tokens at end of #ifdef directive 4 | #ifdef DEBUG#include "../../../debug.h" | ^ aliens.cpp:8:223: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:234: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:237: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:272: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:275: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:346: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vii = vector<ii>;const ll LINF = (ll) 1e18;/** * @brief Li Chao Tree with dynamically created nodes */class li_chao_tree { private: struct line { long long m, b; }; long long eval(const line &f, long long x) { return f.m * x + f.b; } struct node { node *left, *right; line f; long long l, r; node(long long _l, long long _r) : l(_l), r(_r) { left = right = nullptr; f = {0, LINF}; } } *root; void add(node *cur, line nf) { long long m = (cur->l + cur->r) / 2; bool bl = eval(nf, cur->l) < eval(cur->f, cur->l); bool bm = eval(nf, m) < eval(cur->f, m); if (bm) swap(cur->f, nf); if (cur->r - cur->l == 1) return; if (bl != bm) { if (cur->left == nullptr) cur->left = new node(cur->l, m); add(cur->left, nf); } else { if (cur->right == nullptr) cur->right = new node(m, cur->r); add(cur->right, nf); } } long long query(node *cur, long long x) { if (cur == nullptr) return LINF; if (cur->r - cur->l == 1) return eval(cur->f, x); long long m = (cur->l + cur->r) / 2; if (x < m) return min(eval(cur->f, x), query(cur->left, x)); else return min(eval(cur->f, x), query(cur->right, x)); } public: li_chao_tree(long long l, long long r) { root = new node(l, r); } void add(long long m, long long b) { add(root, {m, b}); } long long query(long long x) { return query(root, x); }};long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i < n; i++) if (r[i] > c[i]) swap(r[i], c[i]); vii segments; for (int i = 0; i < n; i++) segments.push_back({r[i], c[i]}); sort(segments.begin(), segments.end(), [&](const ii &a, const ii &b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; }); vi nr = {segments[0].first}, nc = {segments[0].second}; for (int i = 1; i < n; i++) { if (!(nr.back() <= segments[i].first && segments[i].second <= nc.back())) { nr.push_back(segments[i].first); nc.push_back(segments[i].second); } } swap(r, nr); swap(c, nc); n = (int) r.size(); debug(r, c); vector<vll> dp(n + 1, vll(k + 1, LINF)); dp[0].assign(k + 1, 0); vector<li_chao_tree> lct(k + 1, li_chao_tree(0, 0)); for (int j = 0; j <= k; j++) lct[j] = li_chao_tree(0, 2*m); for (int j = 0; j < k; j++) lct[j].add(-2 * r[0], (ll) r[0] * r[0] - 2 * r[0]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) dp[i][j] = lct[j - 1].query(c[i - 1]) + (ll) (c[i - 1] + 1) * (ll) (c[i - 1] + 1); if (i < n) for (int j = 0; j <= k; j++) { lct[j].add(-2 * r[i], dp[i][j] + (ll) r[i] * r[i] - 2 * r[i] - max(0ll, (ll) c[i - 1] - r[i] + 1) * max(0ll, (ll) c[i - 1] - r[i] + 1)); } } debug(dp); *return dp[n][k];} | ^ aliens.cpp:8:349: error: extended character is not valid in an identifier 8 | using ii = pair<int, int>;using ll = long long;using