oj.uz

Submission #557218

# Submission time Handle Problem Language Result Execution time Memory
557218 2022-05-04T21:29:31 Z n0sk1ll Rice Hub (IOI11_ricehub) C++14
68 / 100
 176 ms 37456 KB 
#include "ricehub.h"
#include<bits/stdc++.h>

using namespace std;
long long int typedef li;

//1-root obicnog, 2-root kurca
int val[10000007],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 1 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 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 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 2 ms 304 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 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 568 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 312 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 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 2 ms 444 KB Output is correct
15 Correct 2 ms 316 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 440 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 10 ms 328 KB Output is correct
22 Correct 9 ms 384 KB Output is correct
23 Correct 6 ms 608 KB Output is correct
24 Correct 6 ms 596 KB Output is correct
25 Correct 11 ms 1324 KB Output is correct
26 Correct 8 ms 1344 KB Output is correct
27 Correct 13 ms 1324 KB Output is correct
28 Correct 9 ms 1348 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2468 KB Output is correct
2 Correct 46 ms 2520 KB Output is correct
3 Correct 167 ms 37352 KB Output is correct
4 Incorrect 176 ms 37456 KB Output isn't correct
5 Halted 0 ms 0 KB -