oj.uz

Submission #792694

# Submission time Handle Problem Language Result Execution time Memory
792694 2023-07-25T08:08:02 Z Valters07 Measures (CEOI22_measures) C++14
35 / 100
 456 ms 24160 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),
      		updlzy(pos*2,r-mid);
        else
            setupd(p,val,sz,mid+1,r,pos*2+1),
      		updlzy(pos*2+1,mid-l+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 283 ms 22012 KB Output is correct
2 Correct 303 ms 24096 KB Output is correct
3 Correct 292 ms 23904 KB Output is correct
4 Correct 288 ms 21732 KB Output is correct
5 Correct 289 ms 23012 KB Output is correct
6 Correct 294 ms 22148 KB Output is correct
7 Correct 286 ms 23144 KB Output is correct
8 Correct 289 ms 21864 KB Output is correct
9 Correct 285 ms 21892 KB Output is correct
10 Correct 288 ms 24160 KB Output is correct
11 Correct 323 ms 22536 KB Output is correct
12 Correct 316 ms 23484 KB Output is correct
13 Correct 299 ms 21804 KB Output is correct
14 Correct 289 ms 23756 KB Output is correct
15 Correct 306 ms 23692 KB Output is correct
16 Correct 290 ms 21312 KB Output is correct
17 Correct 291 ms 23080 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 22012 KB Output is correct
2 Correct 303 ms 24096 KB Output is correct
3 Correct 292 ms 23904 KB Output is correct
4 Correct 288 ms 21732 KB Output is correct
5 Correct 289 ms 23012 KB Output is correct
6 Correct 294 ms 22148 KB Output is correct
7 Correct 286 ms 23144 KB Output is correct
8 Correct 289 ms 21864 KB Output is correct
9 Correct 285 ms 21892 KB Output is correct
10 Correct 288 ms 24160 KB Output is correct
11 Correct 323 ms 22536 KB Output is correct
12 Correct 316 ms 23484 KB Output is correct
13 Correct 299 ms 21804 KB Output is correct
14 Correct 289 ms 23756 KB Output is correct
15 Correct 306 ms 23692 KB Output is correct
16 Correct 290 ms 21312 KB Output is correct
17 Correct 291 ms 23080 KB Output is correct
18 Incorrect 456 ms 22960 KB Output isn't correct
19 Halted 0 ms 0 KB -