Submission #243319

#	Time	Username	Problem	Language	Result	Execution time	Memory
243319		Benq	Holiday (IOI14_holiday)	C++14	47 / 100	4140 ms	7532 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
 
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define ins insert
#define pb push_back
 
template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
 
const int mx = 100005;
const int DIFF = 30;
int n;
int S;
int d;
vl w;
 
void reversedir(){
	S = n-1-S;
	reverse(all(w));
}
 
//////TOPK SECTION BEGINS
int k;
int topksize;
ll topksum;
int typ[mx]; //0--> unused, 1--> topk, 2--> couldtake
 
struct cmp1
{
    bool operator()(const int& a, const int& b)
    {
        return w[a] > w[b];
    }
};
 
struct cmp2
{
    bool operator()(const int& a, const int& b)
    {
        return w[a] < w[b];
    }
};
 
priority_queue<int, vector<int>, cmp1> topk; // top <= k
priority_queue<int, vector<int>, cmp2> couldtake; // not part of top k
 
void CLEAR(){
    topksize = 0;
    topksum = 0;
    for(int i = 0; i < n; i++){
        typ[i] = 0;
    }
  topk = priority_queue<int, vector<int>, cmp1>();
  couldtake = priority_queue<int, vector<int>, cmp2>();
 
    //Reset Everything
}
 
void REMOV(){ //removes irrelevant numbers from the top
    while(sz(topk)){
        if(typ[topk.top()] == 0){
            topk.pop();
        }
        else break;
    }
    while(sz(couldtake)){
        if(typ[couldtake.top()] == 0){
            couldtake.pop();
        }
        else break;
    }
}
 
void CHECK(){ //update couldtake, topk
    REMOV();
    while(sz(couldtake) && topksize < k){
    	REMOV();
        int a = couldtake.top();
        couldtake.pop();
        assert(typ[a] == 2);
        topk.push(a);
        typ[a] = 1;
        topksize++;
        topksum+=w[a];
 
        REMOV();
    }
 
    while(topksize == k && sz(couldtake)){
    	REMOV();
        int a = couldtake.top();
        int b = topk.top();
        if(w[a] > w[b]){
            couldtake.pop();
            topk.pop();
            typ[a] = 1;
            typ[b] = 2;
            topk.push(a);
            couldtake.push(b);
            topksum+=w[a];
            topksum-=w[b];
 
        }
        else break;
    }
    REMOV();
}
 
void INSERT(int ind){
    typ[ind] = 2;
    couldtake.push(ind);
    CHECK();
}
 
void ERASE(int ind){
    assert(typ[ind] != 0);
    if(typ[ind] == 1){
        topksize--;
        topksum-=w[ind];
    }
    typ[ind] = 0;
    CHECK();
}
 
//TOPK SECTION ENDS
 
 
ll solvefixedlengthdirection(int len){ //going left to right
	CLEAR();
	k = len;
	int days = d-len;
	int lastr = -5; //last r that is still in topk or couldtake
	ll ans = 0;
	for(int i = S; i >= 0; i--){
		int curr = (days-(S-i))+i;
		ckmin(curr, n-1);
		if(curr-i+1 < len) continue;
 
		if(lastr == -5){
			for(int j = i; j <= curr; j++){
				INSERT(j);
			}
			lastr = curr;
		}
		else{
			while(lastr > curr){
				ERASE(lastr);
				lastr--;
			}
			INSERT(i);
		}
 
		if(topksize == len){
			ckmax(ans, topksum);
		}
	}
	return ans;
}
 
ll solvefixedlength(int len){
	if(len <= 0 || len > n) return 0;
	ll ans = 0;
	
	ckmax(ans, solvefixedlengthdirection(len));
	reversedir();
	ckmax(ans, solvefixedlengthdirection(len));
	return ans;
}
 
ll solverightonly(int L, int days){ //only move right from L
	set<pi> taken;
	ll ans = 0;
	ll cursum = 0;
	for(int i = L; i < n; i++){
		int num = days-(i-L);
		if(num <= 0) break;
		if(sz(taken) > num){
			assert(num == sz(taken)-1);
			pi lowest = *(taken.begin());
			taken.erase(lowest);
			cursum-=lowest.f;
		}
		pi couldtake = mp(w[i], i);
		if(sz(taken) < num){
			taken.ins(couldtake);
			cursum+=couldtake.f;
		}
		else{
			pi lowest = *(taken.begin());
			if(lowest.f < couldtake.f){
				taken.erase(lowest);
				cursum-=lowest.f;
				taken.ins(couldtake);
				cursum+=couldtake.f;
			}
		}
		ckmax(ans, cursum);
	}
 
	return ans;
}
 
 
ll solve(){ //go left, then right
	if(d == 0) return 0;
	clock_t c = clock();
	ll ans = 0;
	ckmax(ans, solverightonly(S, d));
	
	reversedir();
	ckmax(ans, solverightonly(S, d));
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
	int lo = 1;
	int hi = min(n, d+1);
	
	while(hi-lo > 3){
		int mid1 = (2*lo+hi)/3;
		int mid2 = (2*hi+lo)/3;
		ll ans1 = solvefixedlength(mid1);
		//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
		ll ans2 = solvefixedlength(mid2);
		//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
		if(ans1 == 0){
			lo = mid1;
		}
		else if(ans2 == 0){
			hi = mid2;
		}
		else if(ans1 > ans2){
			hi = mid2;
		}
		else{
			lo = mid1;
		}
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
	lo = (lo+hi)/2;
 
	for(int i = 0; i <= DIFF; i++){
		ckmax(ans, solvefixedlength(lo-i));
		ckmax(ans, solvefixedlength(lo+i));
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
 
	return ans;
}
 
ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
	cout << fixed << setprecision(10);
	n = _n;
	S = start;
	d = _d;
	for(int i = 0; i < n; i++){
		w.pb(attraction[i]);
	}
 
    return solve();
}

Compilation message (stderr)

holiday.cpp: In function 'll solve()':
holiday.cpp:219:10: warning: unused variable 'c' [-Wunused-variable]
  clock_t c = clock();
          ^

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