QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225715#7523. Partially Free Mealammardab3anWA 0ms3584kbC++142.8kb2023-10-25 01:41:492023-10-25 01:41:50

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 01:41:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3584kb
  • [2023-10-25 01:41:49]
  • 提交

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'