Submission #131541

#	Time	Username	Problem	Language	Result	Execution time	Memory
131541		MAMBA	Holiday (IOI14_holiday)	C++17	100 / 100	1586 ms	15184 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)

typedef long long ll;
#define int long long

bool smax(ll &a, ll b) { 
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

const int N = 1e5 + 10;

int S[N], m;
ll seg[N << 2], sum[N << 2];

void build(int l = 0, int r = m, int id = 1) {
	seg[id] = sum[id] = 0;
	if (l == r - 1) return;
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r, id << 1 | 1);
}

void segAdd(int pos , int l = 0 , int r = m , int id = 1) {
	if (l == r - 1) {
		seg[id]++;
		sum[id] += S[l];
		return;
	}

	int mid = l + r >> 1;
	if (pos < mid) segAdd(pos , l, mid , id << 1);
	else segAdd(pos , mid , r, id <<1 | 1);

	seg[id] = seg[id <<1] + seg[id <<1 | 1];
	sum[id] = sum[id << 1] + sum[id <<1 | 1];

}

ll segGet(int &rem , int l = 0, int r = m, int id = 1) {
	if (rem <= 0) return 0;
	if (rem >= seg[id]) {
		rem -= seg[id];
		return sum[id];
	}
	if (l == r - 1) {
		ll rem2 = rem;
		rem = 0;
		return rem2 * S[l];
	}
	int mid = l +r >> 1;
	ll res = segGet(rem , mid , r ,id << 1 | 1);
	res += segGet(rem , l , mid , id <<1 ) ;
	return res;
}


ll ans[4][N << 2];


struct dat {
	int l , r , s , t;
	dat (int s_ , int t_, int l_, int r_) {
		s = s_;
		t = t_;
		l = l_;
		r = r_;
	}
};

ll A[N], n, d;


void bfs(int beg, ll res[], int cost) {
	build();
	queue<dat> q;
	fill(res , res + d + 1 , 0);
	q.push(dat(0 , d + 1 , beg , n));

	if (beg == n) return;

	int last = beg;
	while (!q.empty()) {
		auto me = q.front();
		q.pop();
		int mid = me.s + me.t >> 1;

		if (last > me.l + 1) {
			build();
			last = beg;
		}



		int best = me.l;
		rep(i , me.l , me.r) {
			while (last <= i) {
				int id = lower_bound(S , S + m, A[last]) - S;
				segAdd(id);
				last++;
			}
			int rem = mid - (i - beg + 1) * cost;

			if (smax(res[mid] , segGet(rem)))
				best = i;
		}

		if (mid != me.s) q.push(dat(me.s , mid , me.l , best + 1));
		if (mid != me.t - 1) q.push(dat(mid + 1 , me.t , best , me.r));

	}
}

ll findMaxAttraction(int32_t n2, int32_t St, int32_t d2, int32_t A2[]) {

	 n = n2;
	 d = d2;

	rep(i , 0 , n) S[i] = A[i] = A2[i];
	sort(S , S + n);
	m = unique(S , S + n) - S;

	bfs(St + 1 , ans[0] , 1);
	bfs(St + 1 , ans[1] , 2);
	reverse(A , A + n);
	St = n - 1 - St;
	bfs(St + 1 , ans[2] , 1);
	bfs(St + 1 , ans[3] , 2);




	ll answer = 0;

	rep(i , 1 , d + 1)
		rep(j , 0 , 4) {
		//	cout << i << ' ' << j << " : " << ans[j][i] << endl;
			smax(ans[j][i] , ans[j][i]);
		}
		

	rep(i , 0 , d + 1) {
		smax(answer , ans[0][i] + ans[3][d - i]);
		smax(answer , ans[1][i] + ans[2][d - i]);
		if (i) {
			smax(answer , ans[0][i - 1] + ans[3][d - i] + A[St]);
			smax(answer , ans[1][i - 1] + ans[2][d - i] + A[St]);
		}
	}
	return answer;

}

Compilation message (stderr)

holiday.cpp: In function 'void build(long long int, long long int, long long int)':
holiday.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'void segAdd(long long int, long long int, long long int, long long int)':
holiday.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'll segGet(long long int&, long long int, long long int, long long int)':
holiday.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
holiday.cpp: In function 'void bfs(long long int, ll*, long long int)':
holiday.cpp:94:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = me.s + me.t >> 1;
             ~~~~~^~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53