oj.uz

답안 #697732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697732 2023-02-11T00:02:03 Z hadi 메기 농장 (IOI22_fish) C++17
81 / 100
 1000 ms 41356 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <array>
#include <assert.h>
#include <deque>

using namespace std;

class NoOutput : public std::basic_ostream<char> {

};

template<class V>
NoOutput& operator<<(NoOutput& os, const V& v) {
	return os;
}
NoOutput err;
// ostream& err = cerr;

typedef long long int64 ;
const int64 INF = 1e15L;
const int MAXN = 100000+10;

bool is_sorted(const vector<int>& v) {
	for (size_t i=1; i<v.size(); i++) {
		if (v[i-1] > v[i]) return false;
	}
	return true;
}

// return first index i such that k<=v[i], if not returns v.size()
int lowest_geq(const vector<int>& v, int k) {
	auto it = lower_bound(v.begin(), v.end(), k);
	return it == v.end() ? (int) v.size() : it - v.begin();
}

vector<pair<int,int>> transform_container(const vector<int>& c, std::function<pair<int,int> (int)> &&f)
{
    vector<pair<int,int>> ret;
    std::transform(std::begin(c), std::end(c), std::inserter(ret, std::end(ret)), f);
    return ret;
}

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "[";
	for (auto const& vv: v) 
		os << vv << " ";
	return os << "]";
}

template<typename T>
ostream& operator<<(ostream& os, const deque<T>& v) {
	os << "[";
	for (auto const& vv: v) 
		os << vv << " ";
	return os << "]";
}


template<typename T, typename C>
ostream& operator<<(ostream& os, const pair<T, C>& v) {
	return os << v.first << ":" << v.second;
}

struct IntervalTree {
	int n;
	vector<int64> t; 
	vector<int> key;

	void build(const vector<pair<int,int>> key_value) {
		n = key_value.size();
		t.resize(2*n);
		key.clear();
		for (size_t i=0; i<key_value.size(); i++) {
			key.push_back(key_value[i].first);
			t[n+i] = key_value[i].second;
		}
		assert(is_sorted(key));
		for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
	}

	int get_index(int p) const {
		return t[p+n];
	}

	void set_index(int p, int value) {
		for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
	}

	int64 query_index(int l, int r) const {  // sum on interval [l, r)
		int64 res = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) res += t[l++];
			if (r&1) res += t[--r];
		}
		return res;
	}

	int lowest_geq_index(int v) const {
		return lowest_geq(key, v);
	}

	int64 query(int l_v, int r_v) const {
		return query_index(lowest_geq(key, l_v), lowest_geq(key, r_v));
	}

};


// sum of weight of fishes in column i in rows [x-y)
int64 fish(const IntervalTree & tree, int x, int y) {
	return tree.query(x, y);
}

int N;
map<int, int64> dp_iminus1_down, dp_i_down, dp_iminus1_up, dp_i_up;

// max_{N>=y >= x} DP[i-1,y,down] + fish(i,[x-y)), DP[i-1,y,up] + fish(i,[x-y))
int64 max_1(const IntervalTree& tree_i, int x) {
	//naive
	int64 res = 0;
	for (int y = x; y <= N; y++) {
		err << "max_1(" << x << ") " << (dp_iminus1_down.find(y) != dp_iminus1_down.end() ? dp_iminus1_down[y] : -INF) << " " << (dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) << " " << fish(tree_i, x, y) << endl;
		res = max(res, max(
			dp_iminus1_down.find(y) != dp_iminus1_down.end() ? dp_iminus1_down[y] : -INF, 
			dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) + fish(tree_i, x, y));
	}
	return res;
}

// max_{0<=y<= x} DP[i-1,y,up] + fish(i-1,[y-x))
int64 max_2(const IntervalTree& tree_iminus1, int x) {
	//naive
	int64 res = 0;
	for (int y = 0; y <= x; y++) {
		err << "max_2(" << x << ") " << (dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) << " " << fish(tree_iminus1, y, x) << endl;
		res = max(res, 
			(dp_iminus1_up.find(y) != dp_iminus1_up.end() ? dp_iminus1_up[y] : -INF) + fish(tree_iminus1, y, x));
	}
	return res;
}

int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
	::N = N;
	err << "Input: X=" << X << " Y=" << Y << " W=" << W << endl;

	array<vector<int>, MAXN> column_fish_index;
	for (size_t f=0; f<(size_t)M; f++) {
		column_fish_index[X[f]].push_back(f);
	}

	for (size_t i=0; i<(size_t)N+1; i++) {
		sort(column_fish_index[i].begin(), column_fish_index[i].end(), [&](int f1, int f2) { return Y[f1] < Y[f2]; });
		err << "column_fish_index[" << i << "]=" << column_fish_index[i] << endl;
	}

	IntervalTree tree_iminus1;
	tree_iminus1.build(transform_container(column_fish_index[0], [&Y, &W](int f) { return make_pair(Y[f], W[f]); }));

	dp_iminus1_down = dp_iminus1_up = map<int, int64>();
	dp_iminus1_down[0] = dp_iminus1_up[0] = 0;
	for (size_t c=0; c<=1; c++) {
		for (auto f : column_fish_index[c]) {
			dp_iminus1_up[Y[f]+1] = 0;
		}
	}

	for (size_t i=1; i<(size_t)N+1; i++) {
		err << "Column " << i << endl;
		vector<int> important_rows_i;
		important_rows_i.push_back(0);
		for (size_t c=i-1; c<=i+1; c++) {
			for (auto f : column_fish_index[c]) {
				important_rows_i.push_back(Y[f]+1);
			}
		}
		sort(important_rows_i.begin(), important_rows_i.end());
		//err << "important_rows_i: " << important_rows_i << endl;
		important_rows_i.resize(unique(important_rows_i.begin(), important_rows_i.end()) - important_rows_i.begin());
		err << "important_rows_i: " << important_rows_i << endl;
		
		//fill fish interval tree
		IntervalTree tree_i;
		tree_i.build(transform_container(column_fish_index[i], [&Y, &W](int f) { return make_pair(Y[f], W[f]); }));

		// max_{N>=y >= x} DP[i-1,y,down] + fish(i,[x-y)), DP[i-1,y,up] + fish(i,[x-y))
		deque<pair<int,int64>> max_1_discrete;
		max_1_discrete.push_front(make_pair(N+1, -INF));
		for (map<int, int64>::reverse_iterator x = dp_iminus1_up.rbegin(); x != dp_iminus1_up.rend(); x++) {
			auto prev = max_1_discrete.front();
			max_1_discrete.push_front(make_pair(x->first, 
				max(fish(tree_i, x->first, prev.first) + prev.second, 
					max(dp_iminus1_down[x->first], dp_iminus1_up[x->first])) 
			));
			err << "max_1_discrete[" << x->first << "] p=" << prev << " a)" << (fish(tree_i, x->first, prev.first) + prev.second) << " b)" << dp_iminus1_down[x->first] << " c)" << dp_iminus1_up[x->first] << endl;
		}
		err << "max_1_discrete: " << max_1_discrete << endl;

		deque<pair<int,int64>> max_2_discrete;
		// max_{0<=y<= x} DP[i-1,y,up] + fish(i-1,[y-x))
		for (auto const& x: dp_iminus1_up) {
			if (max_2_discrete.size() > 0) {
				auto prev = max_2_discrete.back();
				max_2_discrete.push_back(
					make_pair(
						x.first,
						max(
							fish(tree_iminus1, prev.first, x.first) + prev.second,
							dp_iminus1_up[x.first]
						)
					)
				);
			} else {
				max_2_discrete.push_back(
					make_pair(
						x.first,						
						dp_iminus1_up[x.first]
					)
				);
			}
		}
		err << "max_2_discrete: " << max_2_discrete << endl;

		dp_i_down = dp_i_up = map<int, int64>();
		for (auto x : important_rows_i) {
			// dp_i_down[x] = max_1(tree_i, x);
			auto max_1_discrete_it = lower_bound(max_1_discrete.begin(), max_1_discrete.end(), x, [](const pair<int, int64>& max_1_disc, int r) { return max_1_disc.first < r; });
			err << "max_1_discrete_it: " << *max_1_discrete_it << endl;
			dp_i_down[x] = max_1_discrete_it == max_1_discrete.end() ? -INF : max_1_discrete_it->second + fish(tree_i, x, max_1_discrete_it->first);
			
			// dp_i_up[x] = max(max_2(tree_iminus1, x), dp_iminus1_down[0]);
			auto max_2_discrete_it = lower_bound(max_2_discrete.rbegin(), max_2_discrete.rend(), x, [](const pair<int, int64>& max_2_disc, int r) { return !(max_2_disc.first <= r); } );
			err << "max_2_discrete_it: " << *max_2_discrete_it << " p=" << (max_2_discrete_it == max_2_discrete.rbegin() ? make_pair<int,int64>(-1,-1) : *prev(max_2_discrete_it)) << endl;
			assert(max_2_discrete_it->first <= x);
			assert(max_2_discrete_it == max_2_discrete.rbegin() || prev(max_2_discrete_it)->first > x);
			dp_i_up[x] = max(max_2_discrete_it->second + fish(tree_iminus1, max_2_discrete_it->first, x), dp_iminus1_down[0]);
			err << "dp[" << i << "," << x << "]=" << dp_i_down[x] << " ^:" << dp_i_up[x] << endl;
		}
		dp_iminus1_down = dp_i_down;
		dp_iminus1_up = dp_i_up;

		tree_iminus1 = tree_i;
	}
	return dp_iminus1_down[0];
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 29796 KB Output is correct
2 Correct 336 ms 36140 KB Output is correct
3 Correct 48 ms 2644 KB Output is correct
4 Correct 47 ms 2644 KB Output is correct
5 Execution timed out 1098 ms 40496 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 498 ms 36288 KB Output is correct
3 Correct 569 ms 41356 KB Output is correct
4 Correct 268 ms 29824 KB Output is correct
5 Correct 325 ms 36140 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2516 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 47 ms 2624 KB Output is correct
11 Correct 49 ms 2624 KB Output is correct
12 Correct 407 ms 31220 KB Output is correct
13 Correct 500 ms 37960 KB Output is correct
14 Correct 341 ms 29808 KB Output is correct
15 Correct 280 ms 21984 KB Output is correct
16 Correct 336 ms 29856 KB Output is correct
17 Correct 419 ms 32708 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 2620 KB Output is correct
2 Correct 48 ms 2516 KB Output is correct
3 Correct 92 ms 5588 KB Output is correct
4 Correct 79 ms 4624 KB Output is correct
5 Correct 129 ms 8124 KB Output is correct
6 Correct 126 ms 8128 KB Output is correct
7 Correct 121 ms 8116 KB Output is correct
8 Correct 127 ms 8020 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2592 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 3 ms 2608 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2592 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 3 ms 2608 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 5 ms 2772 KB Output is correct
17 Correct 77 ms 4304 KB Output is correct
18 Correct 66 ms 4916 KB Output is correct
19 Correct 62 ms 4872 KB Output is correct
20 Correct 54 ms 4792 KB Output is correct
21 Correct 51 ms 4820 KB Output is correct
22 Correct 120 ms 7000 KB Output is correct
23 Correct 23 ms 3112 KB Output is correct
24 Correct 67 ms 4092 KB Output is correct
25 Correct 4 ms 2644 KB Output is correct
26 Correct 19 ms 3124 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2592 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 4 ms 2644 KB Output is correct
11 Correct 3 ms 2608 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2644 KB Output is correct
16 Correct 5 ms 2772 KB Output is correct
17 Correct 77 ms 4304 KB Output is correct
18 Correct 66 ms 4916 KB Output is correct
19 Correct 62 ms 4872 KB Output is correct
20 Correct 54 ms 4792 KB Output is correct
21 Correct 51 ms 4820 KB Output is correct
22 Correct 120 ms 7000 KB Output is correct
23 Correct 23 ms 3112 KB Output is correct
24 Correct 67 ms 4092 KB Output is correct
25 Correct 4 ms 2644 KB Output is correct
26 Correct 19 ms 3124 KB Output is correct
27 Correct 7 ms 2804 KB Output is correct
28 Correct 364 ms 13204 KB Output is correct
29 Correct 662 ms 18072 KB Output is correct
30 Correct 840 ms 17144 KB Output is correct
31 Correct 844 ms 17088 KB Output is correct
32 Correct 425 ms 17336 KB Output is correct
33 Correct 857 ms 17068 KB Output is correct
34 Correct 872 ms 17072 KB Output is correct
35 Correct 280 ms 8312 KB Output is correct
36 Correct 799 ms 17496 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 2620 KB Output is correct
2 Correct 48 ms 2516 KB Output is correct
3 Correct 92 ms 5588 KB Output is correct
4 Correct 79 ms 4624 KB Output is correct
5 Correct 129 ms 8124 KB Output is correct
6 Correct 126 ms 8128 KB Output is correct
7 Correct 121 ms 8116 KB Output is correct
8 Correct 127 ms 8020 KB Output is correct
9 Correct 191 ms 8124 KB Output is correct
10 Correct 103 ms 6556 KB Output is correct
11 Correct 239 ms 10476 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 49 ms 2644 KB Output is correct
19 Correct 47 ms 2644 KB Output is correct
20 Correct 48 ms 2644 KB Output is correct
21 Correct 50 ms 2644 KB Output is correct
22 Correct 218 ms 9192 KB Output is correct
23 Correct 286 ms 13892 KB Output is correct
24 Correct 278 ms 14512 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 29796 KB Output is correct
2 Correct 336 ms 36140 KB Output is correct
3 Correct 48 ms 2644 KB Output is correct
4 Correct 47 ms 2644 KB Output is correct
5 Execution timed out 1098 ms 40496 KB Time limit exceeded
6 Halted 0 ms 0 KB -