oj.uz

Submission #557219

# Submission time Handle Problem Language Result Execution time Memory
557219 2022-05-04T21:30:18 Z n0sk1ll Rice Hub (IOI11_ricehub) C++14
68 / 100
 162 ms 48328 KB 
#include "ricehub.h"
#include<bits/stdc++.h>

using namespace std;
long long int typedef li;

//1-root obicnog, 2-root kurca
li val[10000007]; int L[10000007],R[10000007],idx=2;

void add(int p, int l, int r, int s, int x)
{
    val[p]+=x;
    if (l==r) return;
    int mid=(l+r)/2;
    if (s<=mid)
    {
        if (!L[p]) L[p]=++idx;
        add(L[p],l,mid,s,x);
    }
    else
    {
        if (!R[p]) R[p]=++idx;
        add(R[p],mid+1,r,s,x);
    }
}

int sum(int p, int l, int r, int ll, int rr)
{
    if (!p || ll>r || rr<l) return 0;
    if (ll<=l && rr>=r) return val[p];
    int mid=(l+r)/2;
    return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr);
}

int walk(int p, int l, int r, int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    if (val[L[p]]>=k) return walk(L[p],l,mid,k);
    return walk(R[p],mid+1,r,k-val[L[p]]);
}

li balans(int m)
{
    if (m<=0) return 0;
    int p=walk(1,1,1e9,m/2);
    return ((li)sum(1,1,1e9,1,p)*p-(li)sum(2,1,1e9,1,p))+((li)sum(2,1,1e9,p,1e9)-(li)sum(1,1,1e9,p,1e9)*p);
}

int besthub(int n, int useless, int x[], li b)
{
    int l=0,r=0,mx=0;
    for (;r<n;r++)
    {
        add(1,1,1e9,x[r],1);
        add(2,1,1e9,x[r],x[r]);
        while (balans(r-l+2)>b) add(1,1,1e9,x[l],-1),add(2,1,1e9,x[l],-x[l]),l++;
        //cout<<"["<<l<<","<<r<<"] - "<<balans(r-l+2)<<endl;
        mx=max(mx,r-l+1);
    }
    return mx;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 420 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 9 ms 368 KB Output is correct
22 Correct 8 ms 340 KB Output is correct
23 Correct 6 ms 596 KB Output is correct
24 Correct 6 ms 596 KB Output is correct
25 Correct 7 ms 1620 KB Output is correct
26 Correct 7 ms 1620 KB Output is correct
27 Correct 10 ms 1660 KB Output is correct
28 Correct 10 ms 1608 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3028 KB Output is correct
2 Correct 42 ms 3072 KB Output is correct
3 Correct 162 ms 48328 KB Output is correct
4 Incorrect 160 ms 48316 KB Output isn't correct
5 Halted 0 ms 0 KB -