Submission #1216804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216804		giorgi123glm	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	328 KiB

ricehub

#include "ricehub.h"
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <set>
#include <vector>
using namespace std;

class segment_tree {
    public:
        int siz = 1;
        vector <int> segtree;
        
        segment_tree() {}

        void resize (int n) {
            while (siz < n)
                siz *= 2;
            segtree.resize (2 * siz);
        }

        int get (int ind) {
            int u = siz + ind - 1;
            int ans = 0;
            while (u)
				ans += segtree[u] , u /= 2;
			return ans;
        }

        void update (int L, int R, int K, int u, int l, int r) {
            if (r < L || R < l)
                return;

            if (L <= l && r <= R) {
				segtree[u] += K;
				return;
			}

            const int m = (l + r) / 2;
			update (L, R, K, 2 * u, l, m);
			update (L, R, K, 2 * u + 1, m + 1, r);
        }

        void update (int L, int R, int K) {
            return update (L, R, K, 1, 1, siz);
        }
};

int besthub(int R, int L, int X[], long long B) {
	segment_tree segtree;
	segtree.resize (R + 1);
	for (int i = 0; i < R; i++)
		segtree.update (i, i, abs (X[i] - X[0]));

	int l = 0, r = 0;
	while (r < R && B - X[r] >= 0)
		B -= X[r], r++;
	int ans = r - l;

	for (int i = 1; i < R; i++) {
		// chooce rice hub
		segtree.update (0, i - 1, X[i] - X[i - 1]);
		segtree.update (i, segtree.siz, -(X[i] - X[i - 1]));
		
		if (l <= i - 1)
			B -= ((i - 1) - l + 1) * (X[i] - X[i - 1]);
		if (r >= i)
			B += (r - i + 1) * (X[i] - X[i - 1]);
		while (B < 0) {
			B += segtree.get (l);
			l++;
		}
		while (r < R && B >= segtree.get (r)) {
			B -= segtree.get (r);
			r++;
		}
		while (r < R && segtree.get (l) > segtree.get (r)) {
			B -= segtree.get (l);
			l++;
			B += segtree.get (r);
			r++;
		}
		while (r < R && B >= segtree.get (r)) {
			B -= segtree.get (r);
			r++;
		}

		ans = max (r - l + 1, ans);
	}

	return ans;
}

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