Submission #355629

#	Time	Username	Problem	Language	Result	Execution time	Memory
355629		Mefarnis	Holiday (IOI14_holiday)	C++14	23 / 100	55 ms	5100 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
#define maxn 100003
#define pb push_back
using namespace std;
typedef long long LL;

struct city {
	int val,id,ord;
}ar[maxn];

bool comp1(const city& a , const city& b) {
	return a.val < b.val;
}

bool comp2(const city& a , const city& b) {
	return a.id < b.id;
}

LL sum[4*maxn];
int cnt[4*maxn];

void update(int cx , int cy , int q , int val , int id) {
	if(cy < q || q < cx)
		return;
	cnt[id]++;
	sum[id] += val;
	if(cx == cy)
		return;
	int mid = (cx+cy) >> 1;
	update(cx,mid,q,val,2*id);
	update(mid+1,cy,q,val,2*id+1);
}

LL query(int x , int y , int& rem , int id) {
	if(rem >= cnt[id]) {
		rem -= cnt[id];
		return sum[id];
	}
	if(x == y)
		return 0;
	int mid = (x+y) >> 1;
	LL res = query(mid+1,y,rem,2*id+1);
	if(rem > 0)
		res += query(x,mid,rem,2*id);
	return res;
}

LL findMaxAttraction(int n, int s, int d, int arr[]) {
	for( int i = 0 ; i < n ; i++ ) {
		ar[i].val = arr[i];
		ar[i].id = i;
	}
	sort(ar,ar+n,comp1);
	for( int i = 0 ; i < n ; i++ )
		ar[i].ord = i;
	sort(ar,ar+n,comp2);
	LL ans = 0;
	for( int c = s ; c < n && c <= s+d ; c++ ) {
		int rem = d-(c-s);
		update(0,n-1,ar[c].ord,ar[c].val,1);
		LL val = query(0,n-1,rem,1);
		ans = max(ans,val);
	}
	return ans;
}

/*
int main() {
	int n = 5 , s = 0 , d = 6;
	int arr[5] = {10,2,20,30,1};
	printf("%lld\n",findMaxAttraction(n,s,d,arr));
}
*/

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