Submission #387033

#	Time	Username	Problem	Language	Result	Execution time	Memory
387033		alireza_kaviani	Holiday (IOI14_holiday)	C++11	100 / 100	460 ms	20576 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define all(x)		(x).begin() , (x).end()
#define X			first
#define Y			second

const int MAXN = (1 << 20) + 10;
const int LOG = 20;
const ll INF = 1e18;

ll n , d , start , ql , qr , ans , A[MAXN] , pos[MAXN] , fen[2][MAXN];

void add(int ind , int x , int val){
	for(x++; x < MAXN ; x += x & -x)	fen[ind][x] += val;
}

ll get(int x){
	ll cur = 0 , res = 0;
	for(int i = LOG - 1 ; i >= 0 ; i--){
		int nxt = (cur + (1 << i));
		if(fen[0][nxt] <= x){
			x -= fen[0][nxt];
			res += fen[1][nxt];
			cur = nxt;
		}
	}
	return res;
}

void ins(int x , int f){
	add(0 , pos[x] , 1 * f);
	add(1 , pos[x] , A[x] * f);
}

ll calc(int l , int r){
	while(l < ql)	ins(--ql , 1);
	while(qr < r)	ins(++qr , 1);
	while(ql < l)	ins(ql++ , -1);
	while(r < qr)	ins(qr-- , -1);
	return get(d - (r - l) - (r - start));
}

void solve(int l , int r , int optl , int optr){
	if(r < l)	return;
	int mid = l + r >> 1;
	ll mx = -1 , opt = -1;
	for(int i = optl ; i <= mid && i <= optr ; i++){
		ll cost = calc(i , mid);
		assert(fen[0][1 << LOG] == mid - i + 1);
		if(mx <= cost){
			mx = cost;
			opt = i;
		}
	}
	ans = max(ans , mx);
	solve(l , mid - 1 , optl , opt);
	solve(mid + 1 , r , opt , optr);
}

long long int findMaxAttraction(int N, int START, int D, int attract[]) {
	n = N; start = START; d = D;
	vector<pii> vec;
	for(int i = 0 ; i < n ; i++){
		A[i] = attract[i];
		vec.push_back({A[i] , i});
	}
	sort(all(vec) , greater<pii>());
	for(int i = 0 ; i < n ; i++)	pos[vec[i].Y] = i;
	ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
	reverse(A , A + n);
	reverse(pos , pos + n);
	fill(fen[0] , fen[0] + MAXN , 0);
	fill(fen[1] , fen[1] + MAXN , 0); start = n - start - 1;
	ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int mid = l + r >> 1;
      |            ~~^~~

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