Submission #289978

#	Time	Username	Problem	Language	Result	Execution time	Memory
289978		shayan_p	Holiday (IOI14_holiday)	C++17	100 / 100	682 ms	8592 KiB

holiday

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include"holiday.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
#define data STRANGE

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int> pli;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int cost[maxn], tmp[maxn], idcost[maxn];
int A[maxn], B[maxn];
ll ANS1[3 * maxn], ANS2[3 * maxn];

template<typename T> struct fenwick{
    T fen[maxn];
    void add(int pos, T x){
	for(pos+= 3; pos < maxn; pos+= (pos & -pos))
	    fen[pos]+= x;	
    }
    T ask(int pos){
	T ans = 0;
	for(pos+= 3; pos > 0; pos-= (pos & -pos))
	    ans+= fen[pos];
	return ans;
    }
    int LB(T x){
	int ans = 0;
	for(int i = 19; i >= 0; i--){
	    if(ans + (1<<i) < maxn && fen[ans + (1<<i)] < x)
		ans+= 1<<i, x-= fen[ans];	    
	}
	return ans + 1 - 3;
    }
    void clear(){
	memset(fen, 0, sizeof fen);
    }
};
struct Data{
    fenwick<int> f1;
    fenwick<ll> f2;    
    void add(int id){
	f1.add(idcost[id], 1);
	f2.add(idcost[id], cost[id]);
    }
    void era(int id){
	f1.add(idcost[id], -1);
	f2.add(idcost[id], -cost[id]);	
    }
    void clear(){
	f1.clear();
	f2.clear();
    }
    ll ask(int n){
	return f2.ask( f1.LB(n) );
    }    
};
Data data;

void divide(int l, int r, int L, int R, int *cst, ll *ret, int stp){
    if(l > r){
	while(L < R){
	    data.add(cst[L]);
	    L++;
	}
	return;
    }
    int mid = (l+r) >> 1;
    pli bst = {-1, -1};
    int pos = L;
    while(pos <= R && stp * pos <= mid){
	data.add(cst[pos]);
	bst = max(bst, (pli){ data.ask(mid - stp * pos), pos });
	pos++;
    }
    while(pos > L){
	--pos;
	data.era(cst[pos]);	
    }
    ret[mid] = bst.F;
    divide(l, mid-1, L, bst.S, cst, ret, stp);
    divide(mid+1, r, bst.S, R, cst, ret, stp);
}
ll solve(int n, int start, int d, int a[]){
    int n1 = start, n2 = n-n1;
    for(int i = start; i < n; i++)
	A[i-start] = a[i];
    for(int i = start-1; i >= 0; i--)
	B[start-i-1] = a[i];
    divide(0, 3 * n1 - 1, 0, n1 - 1, B, ANS1, 2);
    data.clear();
    divide(0, 2 * n2 - 1, 0, n2 - 1, A, ANS2, 1);
    data.clear();
    ll ans = ANS2[min(2 * n2-1, d)];
    for(int i = 0; i < 3 * n1 && 2 + i <= d; i++){
	ans = max(ans, ANS1[i] + ANS2[min(2 * n2 -1, d-i-2)]);
    }
    return ans;
}
ll findMaxAttraction(int n, int start, int d, int a[]){
    for(int i = 0; i < n; i++){
	cost[i] = a[i];
	a[i] = i;
	tmp[i] = i;
    }
    sort(tmp, tmp + n, [](int i, int j){ return cost[i] > cost[j]; } );
    for(int i = 0; i < n; i++){
	idcost[ tmp[i] ] = i;
    }
    
    ll ans = solve(n, start, d, a);
    reverse(a, a + n);
    ans = max(ans, solve(n, n-1-start, d, a));
    return ans;
}

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