oj.uz

Submission #1044080

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

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

void Add(int x) {
    int i=lower_bound(V.begin(), V.end(), x)-V.begin()+1+cnt[x];
    cnt[x]++;
    auto p=S.upper_bound(make_pair(x, INF));
    if(S.empty()) {
        S.insert({x, i});
        return;
    }
    if(p==S.end()) {
        p=prev(p);
        X[i]=max(0ll, D-(x-(*p).first));
    }
    else if(p==S.begin()) {
        X[(*p).second]=max(0ll, D-((*p).first-x));
    }
    else {
        X[(*p).second]=max(0ll, D-((*p).first-x));
        p=prev(p);
        X[i]=max(0ll, D-(x-(*p).first));
    }
    S.insert({x, i});
}

int Query() {
    int ret=INF;
    int Y[Nmax]={0}, R[Nmax]={0}, L[Nmax]={0};
    for(int i=1; i<=N+M; i++) Y[i]=Y[i-1]+X[i];
    R[N+M]=Y[N+M], L[1]=Y[1];
    for(int i=2; i<=N+M; i++) L[i]=min(L[i-1], Y[i]);
    for(int i=N+M-1; i>=1; i--) R[i]=max(R[i+1], Y[i]);
    for(int i=1; i<N+M; i++) ret=min(ret, R[i+1]-L[i]);
    return ret;
}

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++) Add(A[i]);
    for(int i=1; i<=M; i++) {
        Add(B[i]);
        int tmp=Query();
        if(tmp%2) cout<<tmp/2<<".5 ";
        else cout<<tmp/2<<" ";
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1573 ms 11200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1573 ms 11200 KB Time limit exceeded
2 Halted 0 ms 0 KB -