oj.uz

Submission #1044058

# Submission time Handle Problem Language Result Execution time Memory
1044058 2024-08-05T06:49:52 Z 변재우(#11009) Measures (CEOI22_measures) C++17
0 / 100
 122 ms 32964 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=200010, INF=1e18;
int N, M, D, sum, A[Nmax], B[Nmax], X[Nmax];
vector<int> V;
multiset<pair<int, int>> S;
map<int, int> cnt;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>D;
    for(int i=1; i<=N; i++) cin>>A[i], V.push_back(A[i]);
    for(int i=1; i<=M; i++) cin>>B[i], V.push_back(B[i]);
    sort(V.begin(), V.end());
    for(int i=1; i<=N; i++) {
        int x=lower_bound(V.begin(), V.end(), A[i])-V.begin()+1+cnt[A[i]];
        cnt[A[i]]++;
        auto p=S.upper_bound(make_pair(A[i], INF));
        if(S.empty()) {
            S.insert({A[i], x}); continue;
        }
        if(p==S.end()) {
            p=prev(p);
            sum-=X[x];
            sum+=(X[x]=max(0ll, D-(A[i]-(*p).first)));
        }
        else if(p==S.begin()) {
            sum-=X[(*p).second];
            sum+=(X[(*p).second]=max(0ll, D-((*p).first-A[i])));
        }
        else {
            sum-=X[(*p).second];
            sum+=(X[(*p).second]=max(0ll, D-((*p).first-A[i])));
            p=prev(p);
            sum-=X[x];
            sum+=(X[x]=max(0ll, D-(A[i]-(*p).first)));
        }
        S.insert({A[i], x});
    }
    for(int i=1; i<=M; i++) {
        int x=lower_bound(V.begin(), V.end(), B[i])-V.begin()+1+cnt[B[i]];
        cnt[B[i]]++;
        auto p=S.upper_bound(make_pair(B[i], INF));
        if(S.empty()) {
            S.insert({B[i], x});
            cout<<"0 ";
            continue;
        }
        if(p==S.end()) {
            p=prev(p);
            sum-=X[x];
            sum+=(X[x]=max(0ll, D-(B[i]-(*p).first)));
        }
        else if(p==S.begin()) {
            sum-=X[(*p).second];
            sum+=(X[(*p).second]=max(0ll, D-((*p).first-B[i])));
        }
        else {
            sum-=X[(*p).second];
            sum+=(X[(*p).second]=max(0ll, D-((*p).first-B[i])));
            p=prev(p);
            sum-=X[x];
            sum+=(X[x]=max(0ll, D-(B[i]-(*p).first)));
        }
        S.insert({B[i], x});
        if(sum%2) cout<<sum/2<<".5 ";
        else cout<<sum/2<<" ";
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 32964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 32964 KB Output isn't correct
2 Halted 0 ms 0 KB -