Submission #243340

#	Time	Username	Problem	Language	Result	Execution time	Memory
243340		rqi	Holiday (IOI14_holiday)	C++14	47 / 100	4305 ms	3400 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;
const int STEP = 100;
const int NUM = 15;
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>(); 
    while(sz(topk)){
    	topk.pop();
    }
    while(sz(couldtake)){
    	couldtake.pop();
    }

    //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 < S) continue;

		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
	return 0;
}


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(ans2 == 0){
			hi = mid2;
		}
		else if(ans1 == 0){
			lo = mid1;
		}
		else if(ans1 > ans2){
			hi = mid2;
		}
		else{
			lo = mid1;
		}
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";
	lo = (lo+hi)/2;
	ll curans = solvefixedlength(lo);
	for(int i = NUM; i >= 1; i--){
		ll newans = solvefixedlength(lo+STEP*i);
		if(newans >= curans){
			curans = newans;
			lo = lo+STEP*i;
			break;
		}
	}
	for(int i = NUM; i >= 1; i--){
		ll newans = solvefixedlength(lo-STEP*i);
		if(newans >= curans){
			curans = newans;
			lo = lo-STEP*i;
			break;
		}
	}
	//cout << lo << "\n";
	for(int i = 0; i <= DIFF; i++){

		ll ans1 = solvefixedlength(lo-i);
		ll ans2 = solvefixedlength(lo+i);
		// if(i == 58668-58157){
		// 	cout << "ANS2" << ans2 << "\n";
		// }
		// if(i % 100 == 0) cout << i << " " << ans1 << " " << ans2 << "\n";
		// if(ans1 > ans){
		// 	cout << i << ans1 << "\n";
		// }
		// if(ans2 > ans){
		// 	cout << i << " " << ans2 << "\n";
		// }
		ckmax(ans, ans1);
		ckmax(ans, ans2);
	}
	//cout << ld(clock()-c)/CLOCKS_PER_SEC << "\n";

	return ans;
}

ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
	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:200: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