Submission #79867

#	Time	Username	Problem	Language	Result	Execution time	Memory
79867		shoemakerjo	Holiday (IOI14_holiday)	C++14	17 / 100	5084 ms	28848 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define pii pair<ll, int>
#define mt make_tuple
//pii has ll for now b/c whatever

#define maxn 100010

vector<pii> stuff;
int n;
int d;
int nums[maxn]; //stores how many attractions are at each index
int indo[maxn]; //stores my index in sorted list

ll segsum[maxn*4];
int segct[maxn*4]; //we will only need to activate and deactivate values

ll unor[maxn]; //only go to this spot once
int unospotr[maxn];
ll dosr[maxn]; //go to this spot and back
int dosspotr[maxn];
ll unol[maxn]; //only go to this spot once
int unospotl[maxn];
ll dosl[maxn]; //go to this spot and back
int dosspotl[maxn];

#define ti tuple<int, int, int, int>

ll query(int amount, int ss = 0, int se = n-1, int si = 0) {
	if (amount <= 0) return 0;
	if (ss == se) return segsum[si];
	int numleft = segct[si*2+1];
	int mid = (ss+se)/2;
	if (numleft >= amount) {
		return query(amount, ss, mid, si*2+1);
	}
	else {
		return segsum[si*2+1] + query(amount - numleft, mid+1, se, si*2+2);
	}
}

void addval(int ii, int ss = 0, int se = n-1, int si = 0) {
	if (ss == se) {
		if (segct[si] == 0) {
			segct[si] = 1;
			// cout << "guy: " << stuff[ss].first << endl;
			segsum[si] += stuff[ss].first;
			// cout << "lo: " << segsum[si] << endl;
		}
		return;
	}
	int mid = (ss+se)/2;
	if (ii <= mid) {
		addval(ii, ss, mid, si*2+1);
	}
	else addval(ii, mid+1, se, si*2+2);
	segct[si] = segct[si*2+1] + segct[si*2+2];
	segsum[si] = segsum[si*2+1] + segsum[si*2+2];
}

ll findMaxAttraction(int nn, int start, int dd, int attraction[]) {

	fill(unor, unor+maxn, -1);
	fill(dosr, dosr+maxn, -1);
	fill(unol, unol+maxn, -1);
	fill(dosl, dosl+maxn, -1);

	n = nn;
	d = dd;
	
	for (int i = 0; i < n; i++) {
		nums[i] = attraction[i];
		// cout << "num " << i << "   ::   " << nums[i] << endl;

		stuff.push_back(pii(nums[i], i));
	}
	sort(stuff.begin(), stuff.end());
	reverse(stuff.begin(), stuff.end());
	for (int i = 0; i < n; i++) {
		indo[stuff[i].second] = i;
	}

	// cout << "here" << endl;

	//first we shall go to the right
	vector<ti> rn; //ranges 
	//the setup is the first value is how much "d" is allocated
	//  the second value is the leftmost guy that checks for me
	//  the third is the rightmost guy that checks for me
	rn.push_back(mt(start, n-1, 0, d));

	while (rn.size()) {

		fill(segsum, segsum+n*4, 0);
		fill(segct, segct+n*4, 0);
		vector<ti> nrn;
		int mproc = start;
		for (ti val : rn) {
			//keep them sorted from left to right
			
			int mc = get<0>(val);
			int me = get<1>(val);
			int qs = get<2>(val);
			int qe = get<3>(val);
			int place = (qs + qe)/2;

			for (int i = mproc; i < mc; i++) addval(indo[i]);

			for (int i = mc; i <= me; i++) {
				addval(indo[i]);
				int numleft = place - (i - start);
				ll cur = query(numleft);
				// cout << "cur: " << cur << endl;
				if (cur > unor[place]) {
					unor[place] = cur;
					unospotr[place] = i;
				}
			}
			mproc = me+1;

			//push back qs to place-1 and place+1 to qe
			if (place-1 >= qs) nrn.push_back(mt(mc, unospotr[place], qs, place-1));
			if (place+1 <= qe) nrn.push_back(mt(unospotr[place], me, place+1, qe));

		}
		rn.clear();
		for (ti thing : nrn) rn.push_back(thing);
	}
	//TEST ABOVE GUY BEFORE DOING ANYTHING ELSE (e.g. tons of copy paste)
	rn.push_back(mt(start, n-1, 0, d));



	while (rn.size()) {

		fill(segsum, segsum+n*4, 0);
		fill(segct, segct+n*4, 0);
		vector<ti> nrn;
		int mproc = start;
		for (ti val : rn) {
			//keep them sorted from left to right
			
			int mc = get<0>(val);
			int me = get<1>(val);
			int qs = get<2>(val);
			int qe = get<3>(val);
			int place = (qs + qe)/2;

			for (int i = mproc; i < mc; i++) addval(indo[i]);

			for (int i = mc; i <= me; i++) {
				addval(indo[i]);
				int numleft = place - 2*(i - start);
				ll cur = query(numleft);
				// cout << "cur: " << cur << endl;
				if (cur > dosr[place]) {
					dosr[place] = cur;
					dosspotr[place] = i;
				}
			}
			mproc = me+1;

			//push back qs to place-1 and place+1 to qe
			if (place-1 >= qs) nrn.push_back(mt(mc, dosspotr[place], qs, place-1));
			if (place+1 <= qe) nrn.push_back(mt(dosspotr[place], me, place+1, qe));

		}
		rn.clear();
		for (ti thing : nrn) rn.push_back(thing);
	}

	//there will be 4 of the above loops (yikes, but should be all similar)

	if (start -1 >= 0) rn.push_back(mt(0, start-1, 0, d));

	while (rn.size()) {

		fill(segsum, segsum+n*4, 0);
		fill(segct, segct+n*4, 0);
		vector<ti> nrn;

		int mproc = start-1;

		for (ti val : rn) {
			//keep them sorted from left to right
			
			int mc = get<0>(val);
			int me = get<1>(val);
			int qs = get<2>(val);
			int qe = get<3>(val);
			int place = (qs + qe)/2;

			for (int i = mproc; i > me; i--) addval(indo[i]);

			for (int i = me; i >= mc; i--) {
				addval(indo[i]);
				int numleft = place - (start - i);
				ll cur = query(numleft);
				// cout << "cur: " << cur << endl;
				if (cur > unol[place]) {
					unol[place] = cur;
					unospotl[place] = i;
				}
			}
			mproc = mc-1;


			//push back qs to place-1 and place+1 to qe
			if (place-1 >= qs) nrn.push_back(mt(unospotl[place], me, qs, place-1));
			if (place+1 <= qe) nrn.push_back(mt(mc, unospotl[place], place+1, qe));
			

		}
		rn.clear();
		for (ti thing : nrn) rn.push_back(thing);
	}

	if (start -1 >= 0) rn.push_back(mt(0, start-1, 0, d));

	while (rn.size()) {

		fill(segsum, segsum+n*4, 0);
		fill(segct, segct+n*4, 0);
		vector<ti> nrn;

		int mproc = start-1;

		for (ti val : rn) {
			//keep them sorted from left to right
			
			int mc = get<0>(val);
			int me = get<1>(val);
			int qs = get<2>(val);
			int qe = get<3>(val);
			int place = (qs + qe)/2;

			for (int i = mproc; i > me; i--) addval(indo[i]);

			for (int i = me; i >= mc; i--) {
				addval(indo[i]);
				int numleft = place - 2*(start - i);
				ll cur = query(numleft);
				// cout << "cur: " << cur << endl;
				if (cur > dosl[place]) {
					dosl[place] = cur;
					dosspotl[place] = i;
				}
			}
			mproc = mc-1;


			//push back qs to place-1 and place+1 to qe
			if (place-1 >= qs) nrn.push_back(mt(dosspotl[place], me, qs, place-1));
			if (place+1 <= qe) nrn.push_back(mt(mc, dosspotl[place], place+1, qe));
			

		}
		rn.clear();
		for (ti thing : nrn) rn.push_back(thing);
	}


	ll ans = 0LL;

	for (int i = 0; i <= d; i++) {
		ans = max(ans, unor[i] + dosl[d-i]);
		ans = max(ans, unol[i] + dosr[d-i]);
	}

    return ans;
}

//TL is 5 seconds, hope for the king of constant

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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