oj.uz

Submission #298371

# Submission time Handle Problem Language Result Execution time Memory
298371 2020-09-12T18:44:04 Z mieszko11b Holiday (IOI14_holiday) C++14
100 / 100
 1720 ms 19192 KB 
#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;

#define X first
#define Y second

int n;
int a[100007];
int ord[100007], pos[100007];

struct SegmentTree {
	int lv;
	vector<int> sum, cnt;
	
	void init(int n) {
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
		sum.assign(2 * lv + 2, 0);
		cnt.assign(2 * lv + 2, 0);
	}
	
	void upd(int w) {
		w /= 2;
		while(w) {
			sum[w] = sum[2 * w] + sum[2 * w + 1];
			cnt[w] = cnt[2 * w] + cnt[2 * w + 1];
			w /= 2;
		}
	}
	
	void add(int i) {
		//~ cout << "add" << i << endl;
		int w = lv + pos[i];
		sum[w] = a[i];
		cnt[w] = 1;
		upd(w);
	}
	
	void remove(int i) {
		//~ cout << "rm" << i << endl;
		int w = lv + pos[i];
		sum[w] = 0;
		cnt[w] = 0;
		upd(w);
	}
	
	int query(int w, int l, int r, int k) {
		if(r < l || k <= 0)
			return 0;
		if(cnt[w] <= k)
			return sum[w];
		return query(2 * w, l, (l + r) / 2, k - cnt[2 * w + 1])
			+ query(2 * w + 1, (l + r) / 2 + 1, r, k);
	}
	
	int query(int k) {
		//~ cout << "query " << k << " = " <<query(1, 0, lv - 1, k) << endl;
		return query(1, 0, lv - 1, k);
	}
};

SegmentTree ST;
ii l[300007], r[300007];
int st;

void calc(int d1, int d2, int i1, int i2, ii *f, int t) {
	if(d2 < d1)
		return ;
		
	int dmid = (d1 + d2) / 2;
	f[dmid].Y = -1e9;
	for(int i = i1 ; i <= i2 ; i++) {
		ST.add(i);
		if(t * (i - i1) <= dmid)
			f[dmid] = max(f[dmid], {ST.query(dmid - t * (i - st)), -i});
	}
	

	
	f[dmid].Y = -f[dmid].Y;
	int imid = f[dmid].Y;
	
	//~ cout << imid << endl;
	
	//~ cout << "calc " << d1 << " " << d2 << " " << i1 << " " << i2 << " " << dmid << " " << imid << endl;
	
	for(int i = imid ; i <= i2 ; i++)
		ST.remove(i);
	calc(dmid + 1, d2, imid, i2, f, t);
	
	for(int i = i1 ; i < imid ; i++)
		ST.remove(i);
	calc(d1, dmid - 1, i1, imid, f, t);
}

ll findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
	int res = 0;
	::n = n;
	for(int i = 0 ; i < n ; i++)
		a[i + 1] = attraction[i];
	start++;
	
	for(int tt = 0 ; tt < 2 ; tt++) {
		memset(l, 0, sizeof l);
		memset(r, 0, sizeof r);
		
		vector<ii> hlp(n);
		for(int i = 0 ; i < n ; i++)
			hlp[i] = {a[i + 1], i + 1};
		sort(hlp.begin(), hlp.end());
		
		for(int i = 0 ; i < n ; i++) {
			ord[i + 1] = hlp[i].Y;
			pos[hlp[i].Y] = i + 1;
		}
		
		ST.init(n);
		st = start;
		calc(1, d, start, n, r, 2);
		
		if(start > 1) {
			start--;
			ST.init(n);
			reverse(a + 1, a + n + 1);
			start = n - start + 1;
			
			for(int i = 0 ; i < n ; i++)
				hlp[i] = {a[i + 1], i + 1};
			sort(hlp.begin(), hlp.end());
			
			for(int i = 0 ; i < n ; i++) {
				ord[i + 1] = hlp[i].Y;
				pos[hlp[i].Y] = i + 1;
			}
			
			st = start;
			calc(1, d, start, n, l, 1);
			reverse(a + 1, a + n + 1);
			start = n - start + 1;
			for(int i = 1 ; i <= d ; i++)
				l[i].Y = n + 1 - l[i].Y;
			start++;
		}
		
		r[0].Y = start;
		l[0].Y = start - 1;
		
		//~ cout << "r:\n";
		//~ for(int i = 0 ; i <= d ; i++)
			//~ cout << i << " " <<r[i].X << " " << r[i].Y << endl;
		//~ cout << "l:\n";
		//~ for(int i = 0 ; i <= d ; i++)
			//~ cout << i << " " <<l[i].X << " " << l[i].Y << endl;
		
		for(int dr = 0 ; dr <= d ; dr++) {
			int dl = d - dr - 1;
			if(dl >= 0)
				res = max(res, r[dr].X + l[dl].X);
		}
		res = max(res, r[d].X);
		
		reverse(a + 1, a + n + 1);
		start = n + 1 - start;
	}
	
	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 7 ms 9728 KB Output is correct
7 Correct 7 ms 9728 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 18516 KB Output is correct
2 Correct 1314 ms 18424 KB Output is correct
3 Correct 1471 ms 18424 KB Output is correct
4 Correct 1213 ms 18520 KB Output is correct
5 Correct 1340 ms 18140 KB Output is correct
6 Correct 481 ms 12224 KB Output is correct
7 Correct 709 ms 14168 KB Output is correct
8 Correct 807 ms 14640 KB Output is correct
9 Correct 421 ms 11708 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9984 KB Output is correct
2 Correct 23 ms 10112 KB Output is correct
3 Correct 20 ms 9984 KB Output is correct
4 Correct 23 ms 9984 KB Output is correct
5 Correct 19 ms 9984 KB Output is correct
6 Correct 12 ms 9856 KB Output is correct
7 Correct 9 ms 9856 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9984 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 19160 KB Output is correct
2 Correct 1720 ms 19192 KB Output is correct
3 Correct 377 ms 14136 KB Output is correct
4 Correct 16 ms 9984 KB Output is correct
5 Correct 11 ms 9856 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 1375 ms 18936 KB Output is correct
9 Correct 1264 ms 19064 KB Output is correct