| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 916654 |
2024-01-26T08:42:39 Z |
mickey080929 |
None (JOI15_walls) |
C++17 |
|
283 ms |
30868 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 2e18;
struct Wall{
ll l, r, id;
bool operator<(const Wall &other) const {
if (r - l == other.r - other.l) return id < other.id;
return r - l < other.r - other.l;
}
};
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
ll n, m;
cin >> n >> m;
vector<Wall> a(n);
vector<ll> b(m);
for (ll i=0; i<n; i++) {
cin >> a[i].l >> a[i].r;
a[i].id = i;
}
sort(a.begin(), a.end());
ll mx = 0, mn = inf;
for (ll i=0; i<m; i++) {
cin >> b[i];
mx = max(mx, b[i]);
mn = min(mn, b[i]);
}
b.erase(unique(b.begin(), b.end()), b.end());
m = b.size();
vector<ll> t = {b[0]};
for (ll i=1; i<m-1; i++) {
if (b[i-1] > b[i] && b[i] < b[i+1])
t.push_back(b[i]);
else if (b[i-1] < b[i] && b[i] > b[i+1])
t.push_back(b[i]);
}
if (m >= 2) t.push_back(b[m-1]);
m = t.size();
b = t;
ll cur = 0;
set<ll> s;
priority_queue<array<ll,3>> pq;
for (ll i=0; i<m; i++) s.insert(i);
for (ll i=0; i<m-1; i++) {
pq.push({-abs(b[i+1] - b[i]), i, i+1});
cur += abs(b[i+1] - b[i]);
}
vector<ll> ans(n, 0);
for (ll i=0; i<n; i++) {
while (!pq.empty() && -pq.top()[0] < a[i].r - a[i].l) {
ll x = pq.top()[1];
ll y = pq.top()[2];
pq.pop();
auto xit = s.lower_bound(x);
if (xit == s.end() || *xit != x) continue;
auto yit = next(xit);
if (yit == s.end() || *yit != y) continue;
auto zit = next(yit);
ll z = -1;
if (zit != s.end()) z = *zit;
cur -= abs(b[x] - b[y]);
if (z != -1) cur -= abs(b[y] - b[z]);
s.erase(yit);
if (z == -1) continue;
if (b[x] > b[y]) {
if (b[x] > b[z]) {
auto wit = next(zit);
s.erase(zit);
if (wit == s.end()) continue;
cur += b[x] - b[z];
pq.push({b[*wit] - b[x], x, *wit});
}
else {
if (xit == s.begin()) {
s.erase(xit);
continue;
}
cur += b[z] - b[x];
auto wit = prev(xit);
s.erase(xit);
pq.push({b[*wit] - b[z], *wit, z});
}
}
else {
if (b[x] < b[z]) {
auto wit = next(zit);
s.erase(zit);
if (wit == s.end()) continue;
cur += b[z] - b[x];
pq.push({b[x] - b[*wit], x, *wit});
}
else {
if (xit == s.begin()) {
s.erase(xit);
continue;
}
cur += b[x] - b[z];
auto wit = prev(xit);
s.erase(xit);
pq.push({b[z] - b[*wit], *wit, z});
}
}
}
if (s.size() == 1) {
if (a[i].r <= mx) ans[a[i].id] = mx - a[i].r;
else if (a[i].l >= mn) ans[a[i].id] = a[i].l - mn;
else ans[a[i].id] = 0;
continue;
}
ll fi = *s.begin();
ll se = *next(s.begin());
if (b[fi] < b[se]) {
if (a[i].l >= b[fi]) {
ans[a[i].id] = a[i].l - b[fi] + cur - (a[i].r - a[i].l) * ((ll)s.size()-1);
}
else {
ans[a[i].id] = b[se] - a[i].r + cur - (b[se] - b[fi]) - (a[i].r - a[i].l) * ((ll)s.size()-2);
}
}
else {
if (a[i].r <= b[fi]) {
ans[a[i].id] = b[fi] - a[i].r + cur - (a[i].r - a[i].l) * ((ll)s.size()-1);
}
else {
ans[a[i].id] = a[i].l - b[se] + cur - (b[fi] - b[se]) - (a[i].r - a[i].l) * ((ll)s.size()-2);
}
}
}
for (ll i=0; i<n; i++) {
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
19912 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2900 KB |
Output is correct |
| 2 |
Correct |
149 ms |
21544 KB |
Output is correct |
| 3 |
Correct |
65 ms |
13132 KB |
Output is correct |
| 4 |
Incorrect |
283 ms |
30868 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
19912 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
