Submission #1191627

#TimeUsernameProblemLanguageResultExecution timeMemory
1191627JooDdae방벽 (JOI15_walls)C++20
0 / 100
99 ms12608 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int n, m, l[200200], r[200200]; ll ans[200200]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i=1;i<=n;i++) cin >> l[i] >> r[i]; vector<int> p; for(int i=1;i<=m;i++) { int x; cin >> x; if(!p.empty() && p.back() == x) continue; if(p.size() > 1 && (p.rbegin()[1] < p.back()) == (p.back() < x)) p.pop_back(); p.push_back(x); } set<int> s; for(int i=0;i<p.size();i++) s.insert(i); priority_queue<array<int, 2>> pq; for(int i=2;i+1<p.size();i++) pq.push({-abs(p[i]-p[i-1]), i}); vector<int> id(n); iota(id.begin(), id.end(), 1); sort(id.begin(), id.end(), [&](auto a, auto b){ return r[a]-l[a] < r[b]-l[b]; }); ll sum = 0; for(int i=2;i+1<p.size();i++) sum += abs(p[i]-p[i-1]); for(int i : id) { while(s.size() > 5 && !pq.empty() && -pq.top()[0] <= r[i]-l[i]) { auto [c, u] = pq.top(); pq.pop(); auto it = s.lower_bound(u); if(*it != u || abs(p[*it] - p[*prev(it)]) != -c) continue; sum += c+c; it = s.erase(s.erase(prev(it))); if(prev(it) != s.begin() && next(it) != s.end()) { auto C = abs(p[*it] - p[*prev(it)]); pq.push({-C, *it}); } } if(s.size() <= 5) { for(auto x : s) { x = p[x]; if(x < l[i]) { int K = l[i]-x; l[i] -= K, r[i] -= K, ans[i] += K; } else if(r[i] < x) { int K = x-r[i]; l[i] += K, r[i] += K, ans[i] += K; } } continue; } ans[i] = sum - 1ll*(r[i]-l[i])*(s.size()-3); auto it = s.rbegin(); ans[i] += max(0, abs(p[*it] - p[*next(it)]) - (r[i]-l[i])); int b = p[*s.begin()], nb = p[*next(s.begin())]; if(b < nb) { if(b < l[i]) ans[i] += l[i]-b, r[i] -= l[i]-b; if(r[i] < nb) ans[i] += nb-r[i]; else ans[i] += r[i]-nb; } else { if(r[i] < b) ans[i] += b-r[i], l[i] += b-r[i]; if(nb < l[i]) ans[i] += l[i]-nb; else ans[i] += nb-l[i]; } } for(int i=1;i<=n;i++) cout << ans[i] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...