oj.uz

Submission #603701

# Submission time Handle Problem Language Result Execution time Memory
603701 2022-07-24T09:54:53 Z 8e7 Holiday (IOI14_holiday) C++17
100 / 100
 1859 ms 14952 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r)cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#include"holiday.h"

ll p[maxn];
struct segtree{
	ll seg[4*maxn], cnt[4*maxn];
	void modify(int cur, int l, int r, int ind) {
		if (r <= l) return;
		if (r - l == 1) {
			if (cnt[cur]) {
				cnt[cur] = 0;
				seg[cur] = 0;	
			} else {
				cnt[cur] = 1;
				seg[cur] = p[l];
			}
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind);
		else modify(cur*2+1, m, r, ind);
		seg[cur] = seg[cur*2] + seg[cur*2+1];
		cnt[cur] = cnt[cur*2] + cnt[cur*2+1];
	}
	ll getval(int cur, int l, int r, int k) {
		if (r <= l || k <= 0) return 0;
		if (cnt[cur] <= k) return seg[cur];
		int m = (l + r) / 2;	
		if (cnt[cur*2+1] >= k) return getval(cur*2+1, m, r, k);
		else return seg[cur*2+1] + getval(cur*2, l, m, k - cnt[cur*2+1]);
	}
} tr;
int n;
void solve(int l, int r, int ql, int qr, vector<int> &a, int stop, vector<ll> &ret) {
	if (r <= l || a.size() == 0) return;
	int m = (l + r) / 2; //solving for f(m)
	//[0, ql) has been inserted into tree
	ll best = -1;
	int bind = ql;
	for (int i = ql;i < qr;i++) {
		tr.modify(1, 0, n, a[i]);
		ll val = tr.getval(1, 0, n, m - i * stop);
		if (val > best) {
			best = val;
			bind = i;
		}
	}
	for (int i = ql;i < qr;i++) tr.modify(1, 0, n, a[i]);
	ret[m] = best;
	solve(l, m, ql, bind+1, a, stop, ret);
	for (int i = ql;i < bind;i++) tr.modify(1, 0, n, a[i]);
	solve(m+1, r, bind, qr, a, stop, ret);	
	for (int i = ql;i < bind;i++) tr.modify(1, 0, n, a[i]);	
}
long long int findMaxAttraction(int N, int st, int d, int H[]) {
	if (d == 0) return 0;
	n = N;
	vector<pii> v(n);	
	vector<int> idx(n);
	for (int i = 0;i < n;i++) v[i] = {H[i], i};
	sort(v.begin(), v.end());
	for (int i = 0;i < n;i++) p[i] = v[i].ff, idx[v[i].ss] = i;
	vector<int> a;
	for (int i = st;i < n;i++) a.push_back(idx[i]);
	vector<ll> l1(2*n+1), l2(2*n+1);		
	vector<ll> r1(2*n+1), r2(2*n+1);		
	solve(0, 2*n+1, 0, a.size(), a, 1, l1);
	solve(0, 2*n+1, 0, a.size(), a, 2, l2);
	a.clear();	
	for (int i = st-1;i >= 0;i--) a.push_back(idx[i]);
	solve(0, 2*n+1, 0, a.size(), a, 1, r1);
	solve(0, 2*n+1, 0, a.size(), a, 2, r2);
	/*
	pary(l1.begin(), l1.end());
	pary(l2.begin(), l2.end());
	pary(r1.begin(), r1.end());
	pary(r2.begin(), r2.end());
	*/
	ll ans = 0;
	if (d < l1.size()) ans = max(ans, l1[d]);
	else ans = max(ans, l1.back());
	if (d-1 < r1.size()) ans = max(ans, r1[d-1]);
	else ans = max(ans, r1.back());

	for (int i = 0;i < l1.size();i++) {
		if (d - i - 2 >= 0) {
			ans = max(ans, l1[i] + (d - i - 2 >= r2.size() ? r2.back() : r2[d - i - 2]));	
		}
	}
	for (int i = 0;i < r1.size();i++) {
		if (d - i - 1 >= 0) {
			ans = max(ans, r1[i] + (d - i-1 >= l2.size() ? l2.back() : l2[d - i-1]));	
		}
	}
    return ans;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:98:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  if (d < l1.size()) ans = max(ans, l1[d]);
      |      ~~^~~~~~~~~~~
holiday.cpp:100:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  if (d-1 < r1.size()) ans = max(ans, r1[d-1]);
      |      ~~~~^~~~~~~~~~~
holiday.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0;i < l1.size();i++) {
      |                 ~~^~~~~~~~~~~
holiday.cpp:105:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    ans = max(ans, l1[i] + (d - i - 2 >= r2.size() ? r2.back() : r2[d - i - 2]));
      |                            ~~~~~~~~~~^~~~~~~~~~~~
holiday.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0;i < r1.size();i++) {
      |                 ~~^~~~~~~~~~~
holiday.cpp:110:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    ans = max(ans, r1[i] + (d - i-1 >= l2.size() ? l2.back() : l2[d - i-1]));
      |                            ~~~~~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 14328 KB Output is correct
2 Correct 697 ms 14284 KB Output is correct
3 Correct 1038 ms 14332 KB Output is correct
4 Correct 689 ms 14232 KB Output is correct
5 Correct 1446 ms 13516 KB Output is correct
6 Correct 347 ms 4504 KB Output is correct
7 Correct 710 ms 7756 KB Output is correct
8 Correct 870 ms 8732 KB Output is correct
9 Correct 242 ms 3788 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1132 KB Output is correct
2 Correct 19 ms 1108 KB Output is correct
3 Correct 18 ms 1108 KB Output is correct
4 Correct 26 ms 1108 KB Output is correct
5 Correct 21 ms 1036 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 9 ms 724 KB Output is correct
8 Correct 7 ms 844 KB Output is correct
9 Correct 7 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 14328 KB Output is correct
2 Correct 1127 ms 14336 KB Output is correct
3 Correct 772 ms 7064 KB Output is correct
4 Correct 24 ms 980 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 1827 ms 14952 KB Output is correct
9 Correct 1859 ms 14920 KB Output is correct