oj.uz

Submission #992096

# Submission time Handle Problem Language Result Execution time Memory
992096 2024-06-03T22:05:24 Z Savu_Stefan_Catalin Measures (CEOI22_measures) C++14
100 / 100
 233 ms 32288 KB 
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int NMAX=2e5+505;
int ar1[4*NMAX+505],ar2[4*NMAX+505],ar[4*NMAX+505],lazy[4*NMAX+505];
int n,m,d,N,a[NMAX+505],ras,ind[NMAX+505];
pair<int,int> indd[NMAX+505];
void upd(int nod,int val)
{
    ar1[nod]+=val;
    ar2[nod]+=val;
    lazy[nod]+=val;
}
void propag(int nod)
{
    upd(nod*2,lazy[nod]);
    upd(nod*2+1,lazy[nod]);
    lazy[nod]=0;
}
void updatelazy(int st,int dr,int nod,int qa,int qb,int val)
{
    if (qa<=st&&dr<=qb)
    {
        upd(nod,val);
        return ;
    }
    propag(nod);
    int mij=(st+dr)/2;
    if (qa<=mij) updatelazy(st,mij,nod*2,qa,qb,val);
    if (qb>mij) updatelazy(mij+1,dr,nod*2+1,qa,qb,val);
    ar1[nod]=max(ar1[nod*2],ar1[nod*2+1]);
    ar2[nod]=min(ar2[nod*2],ar2[nod*2+1]);
}
void update(int st,int dr,int nod,int poz,int val)
{
    if (st!=dr) propag(nod);
    if (st==dr)
    {
        ar1[nod]=ar2[nod]=val;
        ar[nod]=1;
        return ;
    }
    int mij=(st+dr)/2;
    if (poz<=mij) update(st,mij,nod*2,poz,val);
    else update(mij+1,dr,nod*2+1,poz,val);
    ar1[nod]=max(ar1[nod*2],ar1[nod*2+1]);
    ar2[nod]=min(ar2[nod*2],ar2[nod*2+1]);
    ar[nod]=ar[nod*2]+ar[nod*2+1];
}
int query1(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar[nod];
    }
    int mij=(st+dr)/2,ras1=0,ras2=0;
    if (qa<=mij) ras1=query1(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=query1(mij+1,dr,nod*2+1,qa,qb);
    return ras1+ras2;
}
int querymax(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar1[nod];
    }
    propag(nod);
    int mij=(st+dr)/2,ras1=-1e17,ras2=-1e17;
    if (qa<=mij) ras1=querymax(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=querymax(mij+1,dr,nod*2+1,qa,qb);
    return max(ras1,ras2);
}
int querymin(int st,int dr,int nod,int qa,int qb)
{
    if (qa<=st&&dr<=qb)
    {
        return ar2[nod];
    }
    propag(nod);
    int mij=(st+dr)/2,ras1=1e17,ras2=1e17;
    if (qa<=mij) ras1=querymin(st,mij,nod*2,qa,qb);
    if (qb>mij) ras2=querymin(mij+1,dr,nod*2+1,qa,qb);
    return min(ras1,ras2);
}
void add(int i)
{
    int poz=ind[i];
    updatelazy(1,N,1,poz,N,d);
    update(1,N,1,poz,(query1(1,N,1,1,poz)+1)*d-a[i]);
    ras=max(ras,querymax(1,N,1,poz,N)-querymin(1,N,1,1,poz));
}
void updbeg(int st,int dr,int nod)
{
    ar1[nod]=-1e10;
    ar2[nod]=1e10;
    if (st==dr) return ;
    int mij=(st+dr)/2;
    updbeg(st,mij,nod*2);
    updbeg(mij+1,dr,nod*2+1);
}
signed main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>d;
    for (int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for (int j=1;j<=m;++j)
    {
        cin>>a[j+n];
    }
    N=n+m;
    updbeg(1,N,1);
    for (int i=1;i<=N;++i)
    {
        indd[i].first=a[i];
        indd[i].second=i;
    }
    sort(indd+1,indd+N+1);
    for (int i=1;i<=N;++i)
    {
        ind[indd[i].second]=i;
    }
    for (int i=1;i<=n;++i)
    {
        add(i);
    }
    for (int j=1;j<=m;++j)
    {
        int i=j+n;
        add(i);
        cout<<ras/2;
        if ((ras)%2) {cout<<".5";}
        cout<<" ";
    }
    return 0;
}
/// 1/2*max(d*(j-i)-(a[j]-a[i]))=1/2*max((d*j-a[j])-(d*i-a[i]))=1/2(max(d*i-a[i])-min(d*i-a[i]))
/// 2 3 1 -> 3 1 2 -> 2 3 1

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 8672 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 227 ms 25612 KB Output is correct
10 Correct 220 ms 27216 KB Output is correct
11 Correct 146 ms 27144 KB Output is correct
12 Correct 182 ms 29084 KB Output is correct
13 Correct 140 ms 26772 KB Output is correct
14 Correct 148 ms 27324 KB Output is correct
15 Correct 224 ms 26824 KB Output is correct
16 Correct 145 ms 27216 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28240 KB Output is correct
2 Correct 162 ms 30108 KB Output is correct
3 Correct 163 ms 32084 KB Output is correct
4 Correct 162 ms 29752 KB Output is correct
5 Correct 165 ms 31240 KB Output is correct
6 Correct 156 ms 28392 KB Output is correct
7 Correct 158 ms 29268 KB Output is correct
8 Correct 153 ms 28104 KB Output is correct
9 Correct 154 ms 29780 KB Output is correct
10 Correct 157 ms 30396 KB Output is correct
11 Correct 161 ms 28856 KB Output is correct
12 Correct 159 ms 31524 KB Output is correct
13 Correct 154 ms 29776 KB Output is correct
14 Correct 159 ms 30036 KB Output is correct
15 Correct 168 ms 29780 KB Output is correct
16 Correct 155 ms 29520 KB Output is correct
17 Correct 162 ms 31060 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28240 KB Output is correct
2 Correct 162 ms 30108 KB Output is correct
3 Correct 163 ms 32084 KB Output is correct
4 Correct 162 ms 29752 KB Output is correct
5 Correct 165 ms 31240 KB Output is correct
6 Correct 156 ms 28392 KB Output is correct
7 Correct 158 ms 29268 KB Output is correct
8 Correct 153 ms 28104 KB Output is correct
9 Correct 154 ms 29780 KB Output is correct
10 Correct 157 ms 30396 KB Output is correct
11 Correct 161 ms 28856 KB Output is correct
12 Correct 159 ms 31524 KB Output is correct
13 Correct 154 ms 29776 KB Output is correct
14 Correct 159 ms 30036 KB Output is correct
15 Correct 168 ms 29780 KB Output is correct
16 Correct 155 ms 29520 KB Output is correct
17 Correct 162 ms 31060 KB Output is correct
18 Correct 233 ms 28292 KB Output is correct
19 Correct 233 ms 30032 KB Output is correct
20 Correct 166 ms 30144 KB Output is correct
21 Correct 190 ms 28236 KB Output is correct
22 Correct 194 ms 28496 KB Output is correct
23 Correct 164 ms 28240 KB Output is correct
24 Correct 219 ms 30804 KB Output is correct
25 Correct 152 ms 27980 KB Output is correct
26 Correct 220 ms 29736 KB Output is correct
27 Correct 228 ms 32288 KB Output is correct
28 Correct 195 ms 28496 KB Output is correct
29 Correct 199 ms 29780 KB Output is correct
30 Correct 186 ms 29776 KB Output is correct
31 Correct 208 ms 30036 KB Output is correct
32 Correct 171 ms 29776 KB Output is correct
33 Correct 220 ms 27772 KB Output is correct
34 Correct 188 ms 31060 KB Output is correct