Submission #510797

#	Time	Username	Problem	Language	Result	Execution time	Memory
510797		CodeTiger927	Holiday (IOI14_holiday)	C++14	7 / 100	111 ms	65540 KiB

holiday

using namespace std;

#include"holiday.h"
#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 100005

pair<long long,int> add(pair<long long,int> a,pair<long long,int> b) {
	return make_pair(a.first + b.first,a.second + b.second);
}

struct node {
	node *lp,*rp;
	pair<long long,int> v;
	node(int l,int r) {
		lp = rp = nullptr;
		v = make_pair(0,0);
		if(l == r) return;
		int m = (l + r) >> 1;
		lp = new node(l,m);
		rp = new node(m + 1,r);
	}

	node(node *_lp,node *_rp) {
		lp = _lp;
		rp = _rp;
		v = add(lp -> v,rp -> v);
	}

	node(pair<long long,int> _v) {
		v = _v;
	}

	node* upd(int l,int r,int x,pair<long long,int> d) {
		if(l == r) return new node(add(v,d));
		int m = (l + r) >> 1;
		if(x <= m) return new node(lp -> upd(l,m,x,d),rp);
		return new node(lp,rp -> upd(m + 1,r,x,d));
	}

	pair<long long,int> get(int l,int r,int a,int b) {
		if(a > r || b < l) return make_pair(0,0);
		if(a <= l && b >= r) return v;
		int m = (l + r) >> 1;
		return add(lp -> get(l,m,a,b),rp -> get(m + 1,r,a,b));
	}
};

node* st[MAXN];
int N,S,D;
pair<long long,int> dp[MAXN];

void solve1(int x,int y,int a,int b) {
	if(x > y) return;
	int z = (x + y) >> 1;
	dp[z] = {-1,-1};
	for(int i = a;i <= b;++i) {
		int l = 0;
		int r = N;
		while(l < r) {
			int m = (l + r + 1) >> 1;
			if(st[m] -> get(0,N - 1,z,i).second + (S - z) + (i - z) <= D) {
				l = m;
			}else{
				r = m - 1;
			}
		}
		dp[z] = max(dp[z],{st[l] -> get(0,N - 1,z,i).first,i});
	}
	if(x == y) return;
	solve1(x,z - 1,a,dp[z].second);
	solve1(z + 1,y,dp[z].second,b);
}

void solve2(int x,int y,int a,int b) {
	if(x > y) return;
	int z = (x + y) >> 1;
	if(!dp[z].first) dp[z] = {-1,-1};
	for(int i = a;i <= b;++i) {
		int l = 0;
		int r = N;
		while(l < r) {
			int m = (l + r + 1) >> 1;
			if(st[m] -> get(0,N - 1,i,z).second + (z - S) + (z - i) <= D) {
				l = m;
			}else{
				r = m - 1;
			}
		}
		dp[z] = max(dp[z],{st[l] -> get(0,N - 1,i,z).first,i});
	}
	// cout << z << " " << dp[z].first << " " << dp[z].second << endl;
	if(x == y) return;
	solve2(z + 1,y,a,dp[z].second);
	solve2(x,z - 1,dp[z].second,b);
}



long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	N = n;
	S = start;
	D = d;
    vector<pair<long long,int>> v;
    for(int i = 0;i < N;++i) {
    	v.push_back({-attraction[i],i});
    }
    st[0] = new node(0,N - 1);
    sort(v.begin(),v.end());
    for(int i = 0;i < N;++i) {
    	st[i + 1] = st[i] -> upd(0,N - 1,v[i].second,make_pair(-v[i].first,1));
    }
    solve1(0,S,S,N - 1);
    solve2(S,N - 1,0,S);
    long long ans = 0;
    for(int i = 0;i < N;++i) {
    	ans = max(ans,dp[i].first);
    }
    return ans;
}

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