Submission #551823

#	Time	Username	Problem	Language	Result	Execution time	Memory
551823		CSQ31	Holiday (IOI14_holiday)	C++17	23 / 100	38 ms	5144 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
ll t[4*MAXN];
int cnt[4*MAXN];
void upd(int v,int pos,int l,int r,int val,int c){
	if(l==r){
		t[v] = val;
		cnt[v] = c;
		return;
	}
	int tm = (l+r)/2;
	if(pos<=tm)upd(2*v,pos,l,tm,val,c);
	else upd(2*v+1,pos,tm+1,r,val,c);
	t[v] = t[2*v] + t[2*v+1];
	cnt[v] = cnt[2*v] + cnt[2*v+1];
}
ll query(int v,int l,int r,int k){
	if(cnt[v] == k || l==r)return t[v];
	int tm = (l+r)/2;
	if(cnt[2*v+1] >= k)return query(2*v+1,tm+1,r,k);
	else return t[2*v+1] + query(2*v,l,tm,k-cnt[2*v+1]);
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
	ll ans = 0;
	vector<pair<int,int>>b;
	for(int i=0;i<n;i++)b.push_back({a[i],i});
	sort(b.begin(),b.end());
	vector<int>idx(n);
	for(int i=0;i<n;i++)idx[b[i].second] = i;
	if(start==0){
		d++;
		for(int i=0;i<n;i++){
			d--;
			if(!d)break;
			upd(1,idx[i]+1,1,n,a[i],1);
			ans = max(ans,query(1,1,n,d));
		}
	}
	return ans;
}

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