Submission #298989

#	Time	Username	Problem	Language	Result	Execution time	Memory
298989		ToMmyDong	Rice Hub (IOI11_ricehub)	C++17	49 / 100	53 ms	3064 KiB

ricehub

#include <bits/extc++.h>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& printRng (ostream& os, IT bg, IT ed) {
    os << "{";
    for (IT it=bg; it!=ed; it++) {
        if (it == bg) os << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T>& v) {return printRng(os,ALL(v));}
#else
#define debug(...)
#endif
#include "ricehub.h"

int n;
ll b;
vector<int> pos, pid;


struct Bit {
    int N;
    vector<ll> bit;
    Bit (int sz) : N(sz+3), bit(sz+3) {}
    void add (int x, ll val) {
        for (x++; x<N; x+=-x&x) {
            bit[x] += val;
        }
    }
    ll qry (int x) {
        ll res = 0;
        for (x++; x; x-=-x&x) {
            res += bit[x];
        }
        return res;
    }
};

bool check (int len) {
    Bit sum(n);
    for (int i=0; i<n; i++) {
        sum.add(i, pos[i]);
        if (i >= len - 1) {
            int pmid = i - len/2;
            ll L = 1LL*pos[pmid]*(len-len/2) - sum.qry(pmid);
            ll R = sum.qry(n) - sum.qry(pmid) - 1LL*pos[pmid]*(len/2);
            if (L + R < b) {
                return true;
            }

            sum.add(i-len+1, -pos[i-len+1]);
        }
    }
    return false;
}

int besthub(int R, int L, int X[], long long B) {
    n = R;
    b = B;
    for (int i=0; i<R; i++) {
        pos.eb(X[i]);
    } 

    int l = 1, r = R + 1;
    while (l < r - 1) {
        int m = (l + r) >> 1;
        if (check(m)) {
            l = m;
        } else {
            r = m;
        }
    }

    return l;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 32 / 32