QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #137825 | #6343. Bitaro's travel | Asymmetry# | Compile Error | / | / | C++20 | 3.7kb | 2023-08-10 18:00:45 | 2024-07-04 01:31:07 |
Judging History
你现在查看的是最新测评结果
- [2024-07-04 01:31:07]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-08-10 18:00:45]
- 提交
answer
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
int INF = int(1e9);
struct SegTree {
vector<int> st;
int leaves;
SegTree(vector<int> t) {
debug(t);
int n = ssize(t);
leaves = 1;
while (leaves < n)
leaves <<= 1;
st.resize(leaves << 1, -INF);
REP (i, n)
st[i + leaves] = t[i];
for (int i = leaves - 1; i; --i)
st[i] = max(st[i * 2], st[i * 2 + 1]);
debug(st);
}
// pierwszy na lewo od poz większy
int find(int poz, int val) {
debug(poz, val);
debug(st);
int lf = leaves, rg = poz + leaves + 1;
vector<int> left, right;
while (lf < rg) {
debug(lf, rg);
if (lf & 1) {
left.emplace_back(lf);
++lf;
}
if (rg & 1)
right.emplace_back(rg - 1);
lf >>= 1;
rg >>= 1;
}
right.insert(right.end(), left.rbegin(), left.rend());
debug(right);
for (int v : right) {
if (st[v] > val) {
debug(v);
while (v < leaves) {
debug(v);
v <<= 1;
if (st[v + 1] > val)
++v;
}
debug(v);
return v - leaves;
}
}
return 0;
}
/*
int find(int poz, int val) {
for (int i = poz; i >= 0; --i)
if (t[i] > val)
return i;
return 0;
}
*/
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> t(n);
REP (i, n)
cin >> t[i];
auto find_start = [&](int x) {
int ind = int(upper_bound(t.begin(), t.end(), x) - t.begin());
int ret = 0;
if (ind < n && abs(t[ret] - x) > abs(t[ind] - x))
ret = ind;
if (ind && abs(t[ret] - x) >= abs(t[ind - 1] - x))
ret = ind - 1;
return ret;
};
auto dist = [&](int p, int q) {
if (p < 0 || q < 0 || p >= n || q >= n)
return INF;
return abs(t[p] - t[q]);
};
debug(t);
vector<int> start_lf(n, n), start_rg(n, -1);
start_lf[n - 1] = -1;
FOR (i, 1, n - 2) {
int bp = -1, bk = n;
while (bk - bp > 1) {
int bs = (bp + bk) / 2;
if (t[bs] - t[i] >= t[i] - t[i - 1])
bk = bs;
else bp = bs;
}
start_lf[i] = bk;
}
debug(start_lf);
start_rg[0] = n;
FOR (i, 1, n - 2) {
int bp = -1, bk = i + 1;
while (bk - bp > 1) {
int bs = (bp + bk) / 2;
if (t[i] - t[bs] > t[i + 1] - t[i])
bp = bs;
else
bk = bs;
}
start_rg[i] = bp;
}
debug(start_rg);
SegTree tree_lf(start_lf);
reverse(start_rg.begin(), start_rg.end());
for (int &i : start_rg)
i = -i;
SegTree tree_rg(start_rg);
int q;
cin >> q;
REP (xd, q) {
int x;
cin >> x;
int cur = find_start(x);
LL ans = abs(t[cur] - x);
int lf = cur, rg = cur;
int side = dist(cur - 1, cur) <= dist(cur, cur + 1);
int cnt = 0;
while (lf || rg < n - 1) {
++cnt;
assert(cnt < 100);
debug(lf, rg, side);
if (side) {
// idziemy w lewo
int poz = tree_lf.find(lf, rg + 1);
debug(poz);
ans += dist(lf, poz);
lf = poz;
if (rg < n - 1) {
ans += dist(lf, rg + 1);
++rg;
side ^= 1;
}
}
else {
// idziemy w prawo
int poz = n - tree_rg.find(n - rg - 1, 1 - lf) - 1;
debug(poz);
ans += dist(rg, poz);
rg = poz;
if (lf) {
ans += dist(rg, lf - 1);
--lf;
side ^= 1;
}
}
}
cout << ans << '\n';
}
}
詳細信息
answer.code:16:9: error: ‘vector’ does not name a type
16 | vector<int> st;
| ^~~~~~
answer.code:19:23: error: expected ‘)’ before ‘<’ token
19 | SegTree(vector<int> t) {
| ~ ^
| )
answer.code: In member function ‘int SegTree::find(int, int)’:
answer.code:38:17: error: ‘vector’ was not declared in this scope
38 | vector<int> left, right;
| ^~~~~~
answer.code:1:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
+++ |+#include <vector>
1 | using namespace std;
answer.code:38:24: error: expected primary-expression before ‘int’
38 | vector<int> left, right;
| ^~~
answer.code:42:33: error: ‘left’ was not declared in this scope
42 | left.emplace_back(lf);
| ^~~~
answer.code:1:1: note: ‘std::left’ is defined in header ‘<ios>’; did you forget to ‘#include <ios>’?
+++ |+#include <ios>
1 | using namespace std;
answer.code:46:33: error: ‘right’ was not declared in this scope
46 | right.emplace_back(rg - 1);
| ^~~~~
answer.code:46:33: note: ‘std::right’ is defined in header ‘<ios>’; did you forget to ‘#include <ios>’?
answer.code:50:17: error: ‘right’ was not declared in this scope
50 | right.insert(right.end(), left.rbegin(), left.rend());
| ^~~~~
answer.code:50:17: note: ‘std::right’ is defined in header ‘<ios>’; did you forget to ‘#include <ios>’?
answer.code:50:43: error: ‘left’ was not declared in this scope
50 | right.insert(right.end(), left.rbegin(), left.rend());
| ^~~~
answer.code:50:43: note: ‘std::left’ is defined in header ‘<ios>’; did you forget to ‘#include <ios>’?
answer.code:53:29: error: ‘st’ was not declared in this scope; did you mean ‘std’?
53 | if (st[v] > val) {
| ^~
| std
answer.code: In function ‘int main()’:
answer.code:79:9: error: ‘cin’ was not declared in this scope
79 | cin.tie(0)->sync_with_stdio(0);
| ^~~
answer.code:1:1: note: ‘std::cin’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’?
+++ |+#include <iostream>
1 | using namespace std;
answer.code:82:9: error: ‘vector’ was not declared in this scope
82 | vector<int> t(n);
| ^~~~~~
answer.code:82:9: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:82:16: error: expected primary-expression before ‘int’
82 | vector<int> t(n);
| ^~~
answer.code:84:24: error: ‘t’ was not declared in this scope
84 | cin >> t[i];
| ^
answer.code: In lambda function:
answer.code:87:43: error: ‘t’ was not declared in this scope
87 | int ind = int(upper_bound(t.begin(), t.end(), x) - t.begin());
| ^
answer.code:87:31: error: ‘upper_bound’ was not declared in this scope
87 | int ind = int(upper_bound(t.begin(), t.end(), x) - t.begin());
| ^~~~~~~~~~~
answer.code:89:32: error: ‘abs’ was not declared in this scope
89 | if (ind < n && abs(t[ret] - x) > abs(t[ind] - x))
| ^~~
answer.code:91:28: error: ‘abs’ was not declared in this scope
91 | if (ind && abs(t[ret] - x) >= abs(t[ind - 1] - x))
| ^~~
answer.code: In lambda function:
answer.code:99:28: error: ‘t’ was not declared in this scope
99 | return abs(t[p] - t[q]);
| ^
answer.code:99:24: error: ‘abs’ was not declared in this scope
99 | return abs(t[p] - t[q]);
| ^~~
answer.code: In function ‘int main()’:
answer.code:104:16: error: expected primary-expression before ‘int’
104 | vector<int> start_lf(n, n), start_rg(n, -1);
| ^~~
answer.code:105:9: error: ‘start_lf’ was not declared in this scope
105 | start_lf[n - 1] = -1;
| ^~~~~~~~
answer.code:110:29: error: ‘t’ was not declared in this scope
110 | if (t[bs] - t[i] >= t[i] - t[i - 1])
| ^
answer.code:118:9: error: ‘start_rg’ was not declared in this scope
118 | start_rg[0] = n;
| ^~~~~~~~
answer.code:123:29: error: ‘t’ was not declared in this scope
123 | if (t[i] - t[bs] > t[i + 1] - t[i])
| ^
answer.code:133:9: error: ‘reverse’ was not declared in this sco...