oj.uz

Submission #1044037

# Submission time Handle Problem Language Result Execution time Memory
1044037 2024-08-05T06:36:45 Z 정희우(#11008) Measures (CEOI22_measures) C++17
0 / 100
 131 ms 13072 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

struct Obj
{
    lint l,r,p,pl,pr;
    bool operator < (const Obj &o) const
    {
        return l<o.l;
    }
    lint merge_(const Obj &o,lint d)
    {
        p=p+o.p;
        pl=min(pl,o.pl);
        pr=max(pr,o.pr);
        l=(pl+pr-p*d)/2;
        r=(pl+pr+p*d)/2;
        return pl-l-d/2;
    }
    void set(lint x,lint d)
    {
        p=1;pl=pr=x;
        l=pl-d/2;
        r=pl+d/2;
    }
};

int n,m;
lint d;
lint ans=0;
set<Obj> st;

void insertp(Obj p)
{
    while(1)
    {
        int flag=0;
        auto it=st.lower_bound(p);
        if(it!=st.end() && p.r>it->l)
        {
            ans=max(ans,p.merge_(*it,d));
            st.erase(it);
            flag=1;
        }
        it=st.lower_bound(p);
        if(it!=st.begin() && p.l<prev(it)->r)
        {
            ans=max(ans,p.merge_(*prev(it),d));
            st.erase(prev(it));
            flag=1;
        }
        if(!flag)break;
    }
    st.insert(p);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> d;d*=2;
    for(int i=0;i<n+m;i++)
    {
        lint x;
        Obj o;
        cin >> x;x*=2;
        o.set(x,d);
        insertp(o);
        if(i>=n)
            cout << (double)ans/2 << ' ';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 13072 KB Output is correct
2 Incorrect 88 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 13072 KB Output is correct
2 Incorrect 88 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -