oj.uz

Submission #792696

# Submission time Handle Problem Language Result Execution time Memory
792696 2023-07-25T08:08:58 Z Valters07 Measures (CEOI22_measures) C++14
45 / 100
 468 ms 24012 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+1,r-mid);
        else
            setupd(p,val,sz,mid+1,r,pos*2+1),
      		updlzy(pos*2,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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 2 ms 464 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 397 ms 21028 KB Output is correct
10 Incorrect 390 ms 21028 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 20108 KB Output is correct
2 Correct 298 ms 22032 KB Output is correct
3 Correct 305 ms 21968 KB Output is correct
4 Correct 338 ms 19844 KB Output is correct
5 Correct 288 ms 21044 KB Output is correct
6 Correct 432 ms 20172 KB Output is correct
7 Correct 305 ms 21220 KB Output is correct
8 Correct 281 ms 19952 KB Output is correct
9 Correct 288 ms 19816 KB Output is correct
10 Correct 312 ms 22184 KB Output is correct
11 Correct 297 ms 20596 KB Output is correct
12 Correct 299 ms 21620 KB Output is correct
13 Correct 342 ms 19880 KB Output is correct
14 Correct 285 ms 21776 KB Output is correct
15 Correct 309 ms 21572 KB Output is correct
16 Correct 287 ms 19780 KB Output is correct
17 Correct 303 ms 21076 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 20108 KB Output is correct
2 Correct 298 ms 22032 KB Output is correct
3 Correct 305 ms 21968 KB Output is correct
4 Correct 338 ms 19844 KB Output is correct
5 Correct 288 ms 21044 KB Output is correct
6 Correct 432 ms 20172 KB Output is correct
7 Correct 305 ms 21220 KB Output is correct
8 Correct 281 ms 19952 KB Output is correct
9 Correct 288 ms 19816 KB Output is correct
10 Correct 312 ms 22184 KB Output is correct
11 Correct 297 ms 20596 KB Output is correct
12 Correct 299 ms 21620 KB Output is correct
13 Correct 342 ms 19880 KB Output is correct
14 Correct 285 ms 21776 KB Output is correct
15 Correct 309 ms 21572 KB Output is correct
16 Correct 287 ms 19780 KB Output is correct
17 Correct 303 ms 21076 KB Output is correct
18 Correct 439 ms 20244 KB Output is correct
19 Incorrect 468 ms 24012 KB Output isn't correct
20 Halted 0 ms 0 KB -