Submission #1012205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012205		NintsiChkhaidze	Holiday (IOI14_holiday)	C++17	100 / 100	291 ms	12232 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define left h*2,l,(l +r)/2
#define right h*2+1,(l + r)/2 + 1,r
using namespace std;
 
const int N = 2e5 + 3;
ll ans = 0,arr[N];
int id,D,rev[N],L,R,n;
map <int,int> mp;
vector <int> vec;
pair <ll,ll> t[4*N];
 
void upd(int h,int l,int r,int idx,int val){
	if (l == r){
		t[h].f += val * rev[l];
		t[h].s += val;
		return;
	}
	if (idx > (l + r)/2) upd(right,idx,val);
	else upd(left,idx,val);
	t[h].f = t[h*2].f + t[h*2+1].f;
	t[h].s = t[h*2].s + t[h*2+1].s;
}
 
ll get(int h,int l,int r,int k){
	if (l == r) {
		ll vl = t[h].f / t[h].s;
		return vl * k;
	}
	
	if (t[h*2 + 1].s >= k) return get(right,k);
	return t[h*2 + 1].f + get(left,k - t[h*2+ 1].s);
}
 
void add(int i){
	upd(1,1,n,arr[i],+1);
}
 
void del(int i){
	upd(1,1,n,arr[i],-1);
}
 
void mo(int l,int r){
	while (L > l) add(--L);
	while (R < r) add(++R);
	while (L < l) del(L++);
	while (R > r) del(R--);
}
 
void go(int l1,int r1,int l2,int r2){
	
	if (l1 > id) return;
	if (l1 > r1) return;
	
	int mid = (l1 + r1)/2,opt = 0;
	ll mx = -1;
	
	for (int i = l2; i <= r2; i++){
		int l = mid,r = i;
		l = min(l,id);
		r = max(r,id);
		
		mo(l,r);
		int len = r - l + min(r - id,id - l);
		int cnt = D - len;
		cnt = min(cnt,r-l+1);
		
		ll cur = 0;
		if (cnt >= t[1].s) cur = t[1].f;
		else if (cnt > 0) cur = get(1,1,n,cnt);
		
		if (cur > mx){
			mx = cur;
			opt = i;
		}
	}
	
	ans=max(ans,mx);
	if (l1 == r1) return;
	go(l1,mid,l2,opt);
	go(mid+1,r1,opt,r2);
}
 
long long int findMaxAttraction(int m, int start, int d, int attraction[]) {
    
    n = m;
    D = d;
    for (int i=0;i<n;i++)
    	arr[i]=attraction[i],vec.push_back(arr[i]);
    
    sort(vec.begin(),vec.end());
    int val=0;
    for (int i=0;i<vec.size();i++){
    	if(!i || vec[i] != vec[i - 1]) ++val;
    	mp[vec[i]] = val;
    	rev[val] = vec[i];
	}
	for (int i=0;i<n;i++)
		arr[i] = mp[arr[i]];
		
	L = 0; R = -1;
    id = start;
    go(0,n - 1,0,n - 1);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=0;i<vec.size();i++){
      |                  ~^~~~~~~~~~~

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