oj.uz

Submission #131541

# Submission time Handle Problem Language Result Execution time Memory
131541 2019-07-17T09:06:18 Z MAMBA Holiday (IOI14_holiday) C++17
100 / 100
 1586 ms 15184 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)

typedef long long ll;
#define int long long

bool smax(ll &a, ll b) { 
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

const int N = 1e5 + 10;

int S[N], m;
ll seg[N << 2], sum[N << 2];

void build(int l = 0, int r = m, int id = 1) {
	seg[id] = sum[id] = 0;
	if (l == r - 1) return;
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r, id << 1 | 1);
}

void segAdd(int pos , int l = 0 , int r = m , int id = 1) {
	if (l == r - 1) {
		seg[id]++;
		sum[id] += S[l];
		return;
	}

	int mid = l + r >> 1;
	if (pos < mid) segAdd(pos , l, mid , id << 1);
	else segAdd(pos , mid , r, id <<1 | 1);

	seg[id] = seg[id <<1] + seg[id <<1 | 1];
	sum[id] = sum[id << 1] + sum[id <<1 | 1];

}

ll segGet(int &rem , int l = 0, int r = m, int id = 1) {
	if (rem <= 0) return 0;
	if (rem >= seg[id]) {
		rem -= seg[id];
		return sum[id];
	}
	if (l == r - 1) {
		ll rem2 = rem;
		rem = 0;
		return rem2 * S[l];
	}
	int mid = l +r >> 1;
	ll res = segGet(rem , mid , r ,id << 1 | 1);
	res += segGet(rem , l , mid , id <<1 ) ;
	return res;
}


ll ans[4][N << 2];


struct dat {
	int l , r , s , t;
	dat (int s_ , int t_, int l_, int r_) {
		s = s_;
		t = t_;
		l = l_;
		r = r_;
	}
};

ll A[N], n, d;


void bfs(int beg, ll res[], int cost) {
	build();
	queue<dat> q;
	fill(res , res + d + 1 , 0);
	q.push(dat(0 , d + 1 , beg , n));

	if (beg == n) return;

	int last = beg;
	while (!q.empty()) {
		auto me = q.front();
		q.pop();
		int mid = me.s + me.t >> 1;

		if (last > me.l + 1) {
			build();
			last = beg;
		}



		int best = me.l;
		rep(i , me.l , me.r) {
			while (last <= i) {
				int id = lower_bound(S , S + m, A[last]) - S;
				segAdd(id);
				last++;
			}
			int rem = mid - (i - beg + 1) * cost;

			if (smax(res[mid] , segGet(rem)))
				best = i;
		}

		if (mid != me.s) q.push(dat(me.s , mid , me.l , best + 1));
		if (mid != me.t - 1) q.push(dat(mid + 1 , me.t , best , me.r));

	}
}

ll findMaxAttraction(int32_t n2, int32_t St, int32_t d2, int32_t A2[]) {

	 n = n2;
	 d = d2;

	rep(i , 0 , n) S[i] = A[i] = A2[i];
	sort(S , S + n);
	m = unique(S , S + n) - S;

	bfs(St + 1 , ans[0] , 1);
	bfs(St + 1 , ans[1] , 2);
	reverse(A , A + n);
	St = n - 1 - St;
	bfs(St + 1 , ans[2] , 1);
	bfs(St + 1 , ans[3] , 2);




	ll answer = 0;

	rep(i , 1 , d + 1)
		rep(j , 0 , 4) {
		//	cout << i << ' ' << j << " : " << ans[j][i] << endl;
			smax(ans[j][i] , ans[j][i]);
		}
		

	rep(i , 0 , d + 1) {
		smax(answer , ans[0][i] + ans[3][d - i]);
		smax(answer , ans[1][i] + ans[2][d - i]);
		if (i) {
			smax(answer , ans[0][i - 1] + ans[3][d - i] + A[St]);
			smax(answer , ans[1][i - 1] + ans[2][d - i] + A[St]);
		}
	}
	return answer;

}

Compilation message

holiday.cpp: In function 'void build(long long int, long long int, long long int)':
holiday.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'void segAdd(long long int, long long int, long long int, long long int)':
holiday.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
holiday.cpp: In function 'll segGet(long long int&, long long int, long long int, long long int)':
holiday.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
holiday.cpp: In function 'void bfs(long long int, ll*, long long int)':
holiday.cpp:94:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = me.s + me.t >> 1;
             ~~~~~^~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8728 KB Output is correct
2 Correct 62 ms 8696 KB Output is correct
3 Correct 99 ms 8700 KB Output is correct
4 Correct 81 ms 8728 KB Output is correct
5 Correct 402 ms 6588 KB Output is correct
6 Correct 163 ms 6748 KB Output is correct
7 Correct 233 ms 4296 KB Output is correct
8 Correct 271 ms 4388 KB Output is correct
9 Correct 124 ms 8444 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 888 KB Output is correct
2 Correct 4 ms 764 KB Output is correct
3 Correct 19 ms 888 KB Output is correct
4 Correct 23 ms 760 KB Output is correct
5 Correct 21 ms 760 KB Output is correct
6 Correct 7 ms 536 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 14056 KB Output is correct
2 Correct 1220 ms 15184 KB Output is correct
3 Correct 478 ms 4320 KB Output is correct
4 Correct 18 ms 632 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 1586 ms 9388 KB Output is correct
9 Correct 1574 ms 9332 KB Output is correct