oj.uz

Submission #171799

# Submission time Handle Problem Language Result Execution time Memory
171799 2019-12-30T12:19:36 Z nickmet2004 Rice Hub (IOI11_ricehub) C++11
0 / 100
 6 ms 760 KB 
#include<bits/stdc++.h>

using namespace std;

int l;
vector<int> f;

void update(int idx , int d){
    ++idx;
    while(idx <= l){
        f[idx] += d;
        idx += idx & (-idx);
    }
}
int sum(int idx){
    long long sum = 0;
    while(idx){
        sum += f[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

int pos , flag , cur_rice;

void Find(int l , int r , long long B){
    int mid = (l + r) >> 1;
    int how_many = sum(r) - sum(l - 1);
    if(how_many * mid <= B && !flag){
        if(how_many > cur_rice){
            pos = mid;
            cur_rice = how_many;
        }
        return;
    }
    int left_side = sum(mid) - sum(l - 1);
    int right_side = sum(r) - sum(mid - 1);
    if(left_side < right_side){
        Find(mid + 1 , r , B);
    } else if(right_side < left_side){
        Find(l , mid - 1 , B);
    } else {
        Find(l , mid - 1 , B);
        Find(mid + 1 , r , B);
    }
}
int besthub(int R , int L , int X[] , long long B){
    l = L;
    int mx = -1;
    for(int i = 0; i < R; ++i){
        update(X[i] , 1);
        mx = max(mx , X[i]);
    }
    Find(0 , mx , B);
    return pos;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -