oj.uz

Submission #719631

# Submission time Handle Problem Language Result Execution time Memory
719631 2023-04-06T12:05:00 Z Rafi22 Measures (CEOI22_measures) C++14
100 / 100
 543 ms 31988 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define ll long long
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007,pot=1<<18;

int id[N],X[N];

int BIT[N];

void ins(int x)
{
    while(x<N)
    {
        BIT[x]++;
        x+=x&(-x);
    }
}
int que(int x)
{
    int res=0;
    while(x>0)
    {
        res+=BIT[x];
        x-=x&(-x);
    }
    return res;
}

int seg[2*pot+7];
int seg1[2*pot+7],lzy1[2*pot+7];
int seg2[2*pot+7],lzy2[2*pot+7];

void push1(int v)
{
    seg[2*v]+=lzy1[v];
    seg[2*v+1]+=lzy1[v];
    seg1[2*v]+=lzy1[v];
    seg1[2*v+1]+=lzy1[v];
    lzy1[2*v]+=lzy1[v];
    lzy1[2*v+1]+=lzy1[v];
    lzy1[v]=0;
}
void ins1(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg1[v]+=x;
        lzy1[v]+=x;
        seg[v]+=x;
        return ;
    }
    if(r<a||l>b) return;
    push1(v);
    ins1(2*v,a,b,l,(l+r)/2,x);
    ins1(2*v+1,a,b,(l+r)/2+1,r,x);
    seg1[v]=max(seg1[2*v],seg1[2*v+1]);
    seg[v]=max({seg[2*v],seg[2*v+1],seg1[2*v]-seg2[2*v+1]});
}

void push2(int v)
{
    seg[2*v]-=lzy2[v];
    seg[2*v+1]-=lzy2[v];
    seg2[2*v]+=lzy2[v];
    seg2[2*v+1]+=lzy2[v];
    lzy2[2*v]+=lzy2[v];
    lzy2[2*v+1]+=lzy2[v];
    lzy2[v]=0;
}
void ins2(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg2[v]+=x;
        lzy2[v]+=x;
        seg[v]-=x;
        return ;
    }
    if(r<a||l>b) return;
    push2(v);
    ins2(2*v,a,b,l,(l+r)/2,x);
    ins2(2*v+1,a,b,(l+r)/2+1,r,x);
    seg2[v]=min(seg2[2*v],seg2[2*v+1]);
    seg[v]=max({seg[2*v],seg[2*v+1],seg1[2*v]-seg2[2*v+1]});
}


signed main()
{
    int n,m,d;
    cin>>n>>m>>d;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]*=2;
    }
    for(int i=0;i<m;i++) cin>>X[i];
    if(n>0)
    {
        d*=2;
        for(int i=0; i<m; i++)
        {
            a.pb(2*X[i]);
            sort(all(a));
            int l=a[0],k=0;
            for(int j=1; j<n+i+1; j++)
            {
                if(l+d>a[j]+k)
                {
                    int m=(l+d-a[j]-k)/2;
                    k+=m;
                    l+=d-m;
                }
                else l=max(a[j]-k,l+d);
            }
            if(k%2==1) cout<<k/2<<".5"<<" ";
            else cout<<k/2<<" ";
        }
    }
    else
    {
        vector<pair<int,int>>V;
        for(int i=0;i<m;i++) V.pb({X[i],i});
        sort(all(V));
        for(int i=0;i<m;i++) id[V[i].nd]=i+1;
        for(int i=0;i<2*pot;i++)
        {
            seg1[i]=-infl;
            seg2[i]=infl;
            seg[i]=-2*infl;
        }
        for(int i=0;i<m;i++)
        {
            ins1(1,id[i]+1,m,1,pot,-d);
            ins2(1,id[i]+1,m,1,pot,-d);
            int k=que(id[i]);
            ins(id[i]);
            ins1(1,id[i],id[i],1,pot,infl+k*d+X[i]-(k+1)*d);
            ins2(1,id[i],id[i],1,pot,-infl+k*d+X[i]-(k+1)*d);
            int x=max(0LL,seg[1]);
            if(x%2==1) cout<<x/2<<".5 ";
            else cout<<x/2<<" ";
        }
    }


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 181 ms 3412 KB Output is correct
10 Correct 229 ms 3396 KB Output is correct
11 Correct 98 ms 3416 KB Output is correct
12 Correct 250 ms 3400 KB Output is correct
13 Correct 96 ms 3408 KB Output is correct
14 Correct 163 ms 3404 KB Output is correct
15 Correct 144 ms 3416 KB Output is correct
16 Correct 114 ms 3396 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 27860 KB Output is correct
2 Correct 360 ms 31020 KB Output is correct
3 Correct 360 ms 30904 KB Output is correct
4 Correct 353 ms 28792 KB Output is correct
5 Correct 369 ms 30104 KB Output is correct
6 Correct 411 ms 29188 KB Output is correct
7 Correct 468 ms 30168 KB Output is correct
8 Correct 376 ms 28948 KB Output is correct
9 Correct 393 ms 28696 KB Output is correct
10 Correct 362 ms 31176 KB Output is correct
11 Correct 422 ms 29572 KB Output is correct
12 Correct 403 ms 30568 KB Output is correct
13 Correct 442 ms 28816 KB Output is correct
14 Correct 394 ms 30792 KB Output is correct
15 Correct 424 ms 30624 KB Output is correct
16 Correct 420 ms 28840 KB Output is correct
17 Correct 407 ms 30204 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 27860 KB Output is correct
2 Correct 360 ms 31020 KB Output is correct
3 Correct 360 ms 30904 KB Output is correct
4 Correct 353 ms 28792 KB Output is correct
5 Correct 369 ms 30104 KB Output is correct
6 Correct 411 ms 29188 KB Output is correct
7 Correct 468 ms 30168 KB Output is correct
8 Correct 376 ms 28948 KB Output is correct
9 Correct 393 ms 28696 KB Output is correct
10 Correct 362 ms 31176 KB Output is correct
11 Correct 422 ms 29572 KB Output is correct
12 Correct 403 ms 30568 KB Output is correct
13 Correct 442 ms 28816 KB Output is correct
14 Correct 394 ms 30792 KB Output is correct
15 Correct 424 ms 30624 KB Output is correct
16 Correct 420 ms 28840 KB Output is correct
17 Correct 407 ms 30204 KB Output is correct
18 Correct 488 ms 29108 KB Output is correct
19 Correct 503 ms 31684 KB Output is correct
20 Correct 386 ms 31900 KB Output is correct
21 Correct 387 ms 29748 KB Output is correct
22 Correct 414 ms 30280 KB Output is correct
23 Correct 391 ms 30116 KB Output is correct
24 Correct 477 ms 30392 KB Output is correct
25 Correct 365 ms 29520 KB Output is correct
26 Correct 542 ms 29480 KB Output is correct
27 Correct 499 ms 31988 KB Output is correct
28 Correct 424 ms 29960 KB Output is correct
29 Correct 490 ms 31288 KB Output is correct
30 Correct 373 ms 29488 KB Output is correct
31 Correct 414 ms 31604 KB Output is correct
32 Correct 377 ms 31368 KB Output is correct
33 Correct 543 ms 29204 KB Output is correct
34 Correct 388 ms 30964 KB Output is correct