oj.uz

Submission #792248

# Submission time Handle Problem Language Result Execution time Memory
792248 2023-07-24T21:09:03 Z Valters07 Measures (CEOI22_measures) C++14
35 / 100
 402 ms 24216 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+15;
const ll INF = 1e18;
struct node
{
    ll mi = INF, mx = -INF, cnt = 0, lzy = 0;
};
node segt[4*N];
int mx;
void updlzy(int pos, int siz)
{
    int lzy = segt[pos].lzy;
    if(lzy)
    {
        segt[pos].mi+=lzy;
        segt[pos].mx+=lzy;
        if(siz>1)
            segt[pos*2].lzy+=lzy,
            segt[pos*2+1].lzy+=lzy;
        segt[pos].lzy=0;
    }
}
void updnode(int pos)
{
    segt[pos].cnt=segt[pos*2].cnt+segt[pos*2+1].cnt;
    segt[pos].mi=min(segt[pos*2].mi,segt[pos*2+1].mi);
    segt[pos].mx=max(segt[pos*2].mx,segt[pos*2+1].mx);
}
void upd(int lb, int rb, ll val, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(rb<l||r<lb)
        return;
    if(lb<=l&&r<=rb)
        segt[pos].lzy+=val,
        updlzy(pos,r-l+1);
    else
    {
        int mid = (l+r)/2;
        upd(lb,rb,val,l,mid,pos*2);
        upd(lb,rb,val,mid+1,r,pos*2+1);
        updnode(pos);
    }
}
void setupd(int p, ll val, int sz, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(l==r)
        segt[pos].mi=segt[pos].mx=val,
        segt[pos].cnt=sz;
    else
    {
        int mid = (l+r)/2;
        if(p<=mid)
            setupd(p,val,sz,l,mid,pos*2);
        else
            setupd(p,val,sz,mid+1,r,pos*2+1);
        updnode(pos);
    }
}
node get1(int lb, int rb, int l = 0, int r = mx, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(rb<l||r<lb)
        return {INF,-INF,0};
    if(lb<=l&&r<=rb)
        return segt[pos];
    int mid = (l+r)/2;
    auto t1 = get1(lb,rb,l,mid,pos*2), t2 = get1(lb,rb,mid+1,r,pos*2+1);
    return {min(t1.mi,t2.mi),max(t1.mx,t2.mx),t1.cnt+t2.cnt};
}
int main()
{
    fio
//    ifstream cin("in.in");
    int n, m, d;
    cin >> n >> m >> d;
    mx=n+m-1;
    vector<pair<int,int> > a(n+m);
    for(int i = 0;i<n+m;i++)
        cin >> a[i].fi,
        a[i].se=i;
    sort(a.begin(),a.end());
    vector<int> ord(n+m);
    for(int i = 0;i<n+m;i++)
        ord[a[i].se]=i;
    ll res = 0;
    for(int i = 0;i<n+m;i++)
    {
        int val = a[ord[i]].fi, pos = ord[i];
        ll cur = d*get1(0,pos).cnt-val;
        setupd(pos,cur,1);
        upd(pos+1,n+m-1,d);
        res=max(res,get1(pos,n+m-1).mx-get1(0,pos-1).mi);
        res=max(res,get1(pos+1,n+m-1).mx-get1(0,pos).mi);
        if(i>=n)
        {
            cout << res/2;
            if(res%2)
                cout << ".5";
            cout << " ";
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 22036 KB Output is correct
2 Correct 282 ms 23944 KB Output is correct
3 Correct 292 ms 23960 KB Output is correct
4 Correct 274 ms 21708 KB Output is correct
5 Correct 276 ms 22988 KB Output is correct
6 Correct 291 ms 22132 KB Output is correct
7 Correct 278 ms 23088 KB Output is correct
8 Correct 274 ms 21824 KB Output is correct
9 Correct 275 ms 21712 KB Output is correct
10 Correct 284 ms 24216 KB Output is correct
11 Correct 278 ms 22592 KB Output is correct
12 Correct 280 ms 23516 KB Output is correct
13 Correct 275 ms 21800 KB Output is correct
14 Correct 303 ms 23688 KB Output is correct
15 Correct 282 ms 23588 KB Output is correct
16 Correct 274 ms 21384 KB Output is correct
17 Correct 274 ms 22996 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 22036 KB Output is correct
2 Correct 282 ms 23944 KB Output is correct
3 Correct 292 ms 23960 KB Output is correct
4 Correct 274 ms 21708 KB Output is correct
5 Correct 276 ms 22988 KB Output is correct
6 Correct 291 ms 22132 KB Output is correct
7 Correct 278 ms 23088 KB Output is correct
8 Correct 274 ms 21824 KB Output is correct
9 Correct 275 ms 21712 KB Output is correct
10 Correct 284 ms 24216 KB Output is correct
11 Correct 278 ms 22592 KB Output is correct
12 Correct 280 ms 23516 KB Output is correct
13 Correct 275 ms 21800 KB Output is correct
14 Correct 303 ms 23688 KB Output is correct
15 Correct 282 ms 23588 KB Output is correct
16 Correct 274 ms 21384 KB Output is correct
17 Correct 274 ms 22996 KB Output is correct
18 Incorrect 402 ms 22996 KB Output isn't correct
19 Halted 0 ms 0 KB -