oj.uz

Submission #719621

# Submission time Handle Problem Language Result Execution time Memory
719621 2023-04-06T11:33:04 Z Rafi22 Measures (CEOI22_measures) C++14
24 / 100
 218 ms 26316 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 seg1[2*pot+7],lzy1[2*pot+7];

void push1(int 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;
        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]);
}

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

void push2(int 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;
        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]);
}


signed main()
{
    int n,m,d;
    cin>>n>>m>>d;
    d*=2;
    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];
        X[i]*=2;
    }
    if(n>0)
    {
        for(int i=0; i<m; i++)
        {
            a.pb(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;
        }
        for(int i=0;i<m;i++)
        {
            ins1(1,id[i]+1,n,1,pot,-d);
            ins2(1,id[i]+1,n,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=seg1[1]-seg2[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 316 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 2 ms 336 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 166 ms 3660 KB Output is correct
10 Correct 207 ms 3664 KB Output is correct
11 Correct 108 ms 3656 KB Output is correct
12 Correct 218 ms 3620 KB Output is correct
13 Correct 94 ms 3648 KB Output is correct
14 Correct 155 ms 3636 KB Output is correct
15 Correct 138 ms 3636 KB Output is correct
16 Correct 131 ms 3612 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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