| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677466 |
2023-01-03T11:56:48 Z |
jhwest2 |
None (JOI15_walls) |
C++14 |
|
610 ms |
29868 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 202020;
const int INF = 1e9 + 10;
int n, m, a[N], b[N], ord[N], dir[N], pmin[N], pmax[N]; ll ans[N];
vector<int> q;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
for (int i = 1; i <= m; i++) {
int x; cin >> x;
if (!q.empty() && q.back() == x)
continue;
if (q.size() >= 2 && (q[q.size() - 2] < q.back()) == (q.back() < x))
q.pop_back();
q.push_back(x);
}
// determine direction
pmin[0] = pmax[0] = q[0];
for (int i = 1; i < q.size(); i++) {
pmin[i] = min(pmin[i - 1], q[i]);
pmax[i] = max(pmax[i - 1], q[i]);
}
for (int i = 1; i <= n; i++) {
int L = 0, R = (int)q.size();
while (L < R) {
int M = (L + R) / 2;
if (pmin[M] < a[i] || pmax[M] > b[i])
R = M;
else
L = M + 1;
}
if (R != q.size()) {
if (pmin[L] < a[i])
dir[i] = 1; // go left
else
dir[i] = 2; // go right
}
}
for (int i = 1; i <= n; i++) {
if (dir[i] == 1)
a[i] += INF, b[i] += INF, ans[i] -= INF;
if (dir[i] == 2)
a[i] -= INF, b[i] -= INF, ans[i] -= INF;
}
for (int i = 1; i <= n; i++)
ord[i] = i;
sort(ord + 1, ord + 1 + n, [&](auto i, auto j) {
return b[i] - a[i] < b[j] - a[j];
});
set<pair<int, int>> st;
set<pair<int, int>> pq;
for (int i = 0; i < q.size(); i++) {
st.insert({i, q[i]});
if (i != 0)
pq.insert({abs(q[i] - q[i - 1]), i - 1});
}
ll len = 0, cnt = (int)q.size() - 1;
for (int i = 1; i < q.size(); i++)
len += abs(q[i] - q[i - 1]);
for (int i = 1; i <= n; i++) {
if (dir[ord[i]] == 0)
continue;
int l = a[ord[i]], r = b[ord[i]];
while (pq.size() >= 2 && pq.begin()->first <= r - l) {
auto [x, y] = *pq.begin(); pq.erase(pq.begin());
--cnt;
auto it = st.lower_bound({y, q[y]});
if (it == st.begin()) {
st.erase(it);
len -= x;
}
else if (next(next(it)) == st.end()) {
st.erase(next(it));
len -= x;
}
else {
pq.erase({abs(it->second - prev(it)->second), prev(it)->first});
it = st.erase(it);
pq.erase({abs(it->second - next(it)->second), it->first});
it = st.erase(it);
pq.insert({abs(it->second - prev(it)->second), prev(it)->first});
--cnt;
len -= 2 * x;
}
}
int s = st.begin()->second;
int t = next(st.begin())->second;
if (cnt == 1) {
if (s < t) {
if (dir[ord[i]] == 1)
ans[ord[i]] += l - s + max(0, t - s - r + l);
else
ans[ord[i]] += t - r;
}
else {
if (dir[ord[i]] == 1)
ans[ord[i]] += l - t;
else
ans[ord[i]] += s - r + max(0, s - t - r + l);
}
}
else {
ans[ord[i]] += len - cnt * (r - l);
if (s < t)
ans[ord[i]] += abs(l - s);
else
ans[ord[i]] += abs(r - s);
}
// cout << i << "!\n";
// for (auto [x, y] : st)
// cout << y << ' ';
// cout << '\n';
// cout << len << ' ' << cnt << ' ' << "?\n";
// cout << l << ' ' << r << ' ' << s << ' '<< t << "!!!\n";
}
for (int i = 1; i <= n; i++)
cout << ans[i] << '\n';
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 1; i < q.size(); i++) {
| ~~^~~~~~~~~~
walls.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if (R != q.size()) {
| ~~^~~~~~~~~~~
walls.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < q.size(); i++) {
| ~~^~~~~~~~~~
walls.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 1; i < q.size(); i++)
| ~~^~~~~~~~~~
walls.cpp:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [x, y] = *pq.begin(); pq.erase(pq.begin());
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
980 KB |
Output is correct |
| 2 |
Correct |
225 ms |
14340 KB |
Output is correct |
| 3 |
Correct |
358 ms |
21404 KB |
Output is correct |
| 4 |
Correct |
323 ms |
21444 KB |
Output is correct |
| 5 |
Correct |
333 ms |
21452 KB |
Output is correct |
| 6 |
Correct |
295 ms |
21440 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
2512 KB |
Output is correct |
| 2 |
Correct |
289 ms |
15736 KB |
Output is correct |
| 3 |
Correct |
91 ms |
9804 KB |
Output is correct |
| 4 |
Correct |
610 ms |
29848 KB |
Output is correct |
| 5 |
Correct |
373 ms |
22788 KB |
Output is correct |
| 6 |
Correct |
531 ms |
29868 KB |
Output is correct |
| 7 |
Correct |
354 ms |
22712 KB |
Output is correct |
| 8 |
Correct |
505 ms |
29844 KB |
Output is correct |
| 9 |
Correct |
82 ms |
6988 KB |
Output is correct |
| 10 |
Correct |
229 ms |
29368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
980 KB |
Output is correct |
| 2 |
Correct |
225 ms |
14340 KB |
Output is correct |
| 3 |
Correct |
358 ms |
21404 KB |
Output is correct |
| 4 |
Correct |
323 ms |
21444 KB |
Output is correct |
| 5 |
Correct |
333 ms |
21452 KB |
Output is correct |
| 6 |
Correct |
295 ms |
21440 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
