QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225715 | #7523. Partially Free Meal | ammardab3an | WA | 0ms | 3584kb | C++14 | 2.8kb | 2023-10-25 01:41:49 | 2023-10-25 01:41:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans[200010];
void solve(const vector<pair<int, int>> &v, int l, int r, int tl, int tr, multiset<pair<int, int>> &f, multiset<pair<int, int>> &s, set<int> &idx, ll sum){
if(tl > tr) return;
int mid = (tl+tr)/2;
pair<ll, ll> best(1e18, -1);
while(f.size() >= mid){
auto [x, y] = *(--f.end());
f.erase(--f.end());
s.insert({x, y});
sum -= x;
}
while(f.size() < mid-1 && !s.empty()){
auto [x, y] = *(s.begin());
s.erase(s.begin());
f.insert({x, y});
sum += x;
}
for(int i = l; i <= r; i++){
if(f.size() == mid-1) best = min(best, {sum + v[i].second + v[i].first, i});
if(i == r) break;
if(idx.count(i) == 0){
s.insert({v[i].first, i});
idx.insert(i);
}
while(f.size() >= mid){
auto [x, y] = *(--f.end());
f.erase(--f.end());
s.insert({x, y});
sum -= x;
}
while(f.size() < mid-1 && !s.empty()){
auto [x, y] = *(s.begin());
s.erase(s.begin());
f.insert({x, y});
sum += x;
}
while(!f.empty() && !s.empty()){
auto [x1, y1] = *(--f.end());
auto [x2, y2] = *s.begin();
if(x1 <= x2) break;
f.erase(--f.end());
s.erase(s.begin());
s.insert({x1, y1});
f.insert({x2, y2});
sum -= x1;
sum += x2;
}
}
ans[mid] = best.first;
while(!idx.empty() && *(--idx.end()) > best.second-1){
int x = *(--idx.end());
idx.erase(--idx.end());
if(f.count({v[x].first, x})){
f.erase({v[x].first, x});
sum -= v[x].first;
}
if(s.count({v[x].first, x})){
s.erase({v[x].first, x});
}
}
solve(v, best.second, r, mid+1, tr, f, s, idx, sum);
while(!idx.empty() && *(--idx.end()) > l){
int x = *(--idx.end());
idx.erase(--idx.end());
if(f.count({v[x].first, x})){
f.erase({v[x].first, x});
sum -= v[x].first;
}
if(s.count({v[x].first, x})){
s.erase({v[x].first, x});
}
}
sum = 0;
solve(v, l, best.second, tl, mid-1, f, s, idx, sum);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<pair<int, int>> v(n);
for(auto &[f, s] : v) cin >> s >> f;
sort(v.begin(), v.end());
for(auto &[f, s] : v) swap(f, s);
multiset<pair<int, int>> f, s;
set<int> idx;
solve(v, 0, n-1, 1, n, f, s, idx, 0);
for(int i = 1; i <= n; i++){
cout << ans[i] << "\n";
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
3 2 5 4 3 3 7
output:
3 11 16
result:
wrong answer 1st lines differ - expected: '7', found: '3'