oj.uz

Submission #792240

# Submission time Handle Problem Language Result Execution time Memory
792240 2023-07-24T20:17:52 Z Valters07 Measures (CEOI22_measures) C++14
35 / 100
 307 ms 24204 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).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 2 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 2 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 201 ms 21984 KB Output is correct
2 Correct 207 ms 23972 KB Output is correct
3 Correct 211 ms 23892 KB Output is correct
4 Correct 201 ms 21732 KB Output is correct
5 Correct 205 ms 23064 KB Output is correct
6 Correct 203 ms 22188 KB Output is correct
7 Correct 206 ms 23156 KB Output is correct
8 Correct 208 ms 21988 KB Output is correct
9 Correct 203 ms 21708 KB Output is correct
10 Correct 210 ms 24204 KB Output is correct
11 Correct 205 ms 22540 KB Output is correct
12 Correct 206 ms 23492 KB Output is correct
13 Correct 213 ms 21792 KB Output is correct
14 Correct 205 ms 23756 KB Output is correct
15 Correct 213 ms 23712 KB Output is correct
16 Correct 201 ms 21320 KB Output is correct
17 Correct 204 ms 23116 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 21984 KB Output is correct
2 Correct 207 ms 23972 KB Output is correct
3 Correct 211 ms 23892 KB Output is correct
4 Correct 201 ms 21732 KB Output is correct
5 Correct 205 ms 23064 KB Output is correct
6 Correct 203 ms 22188 KB Output is correct
7 Correct 206 ms 23156 KB Output is correct
8 Correct 208 ms 21988 KB Output is correct
9 Correct 203 ms 21708 KB Output is correct
10 Correct 210 ms 24204 KB Output is correct
11 Correct 205 ms 22540 KB Output is correct
12 Correct 206 ms 23492 KB Output is correct
13 Correct 213 ms 21792 KB Output is correct
14 Correct 205 ms 23756 KB Output is correct
15 Correct 213 ms 23712 KB Output is correct
16 Correct 201 ms 21320 KB Output is correct
17 Correct 204 ms 23116 KB Output is correct
18 Incorrect 307 ms 22956 KB Output isn't correct
19 Halted 0 ms 0 KB -