Submission #1180501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180501		jbareja	Art Exhibition (JOI18_art)	C++20	30 / 100	1096 ms	840 KiB

art

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SegTree_sum {
	vector<ll> values;
	int base;

	SegTree_sum(vector<ll>& vec) {
		base = 1;
		while (base <= vec.size()) base *= 2;
		values.assign(base * 2, 0);
		for (int i=0; i<vec.size(); i++) values[base + i] = vec[i];
		for (int i=base-1; i>=1; i--) values[i] = values[i*2] + values[i*2+1];
	}

	ll Query(int l, int r) {
		l += base - 1;
		r += base + 1;
		ll ans = 0;
		while (l/2 != r/2) {
			if (l%2 == 0) ans += values[l+1];
			if (r%2 != 0) ans += values[r-1];
			l /= 2, r /= 2;
		}
		return ans;
	}
};

struct SegTree_max {
	vector<ll> values;
	int base;

	SegTree_max(vector<ll>& vec) {
		base = 1;
		while (base <= vec.size()) base *= 2;
		values.assign(base * 2, LLONG_MIN);
		for (int i=0; i<vec.size(); i++) values[base + i] = vec[i];
		for (int i=base-1; i>=1; i--) values[i] = max(values[i*2], values[i*2+1]);
	}

	ll Query(int l, int r) {
		l += base - 1;
		r += base + 1;
		ll ans = LLONG_MIN;
		while (l/2 != r/2) {
			if (l%2 == 0) ans = max(ans, values[l+1]);
			if (r%2 != 0) ans = max(ans, values[r-1]);
			l /= 2, r /= 2;
		}
		return ans;
	}
};

struct SegTree_min {
	vector<ll> values;
	int base;

	SegTree_min(vector<ll>& vec) {
		base = 1;
		while (base <= vec.size()) base *= 2;
		values.assign(base * 2, LLONG_MAX);
		for (int i=0; i<vec.size(); i++) values[base + i] = vec[i];
		for (int i=base-1; i>=1; i--) values[i] = min(values[i*2], values[i*2+1]);
	}

	ll Query(int l, int r) {
		l += base - 1;
		r += base + 1;
		ll ans = LLONG_MAX;
		while (l/2 != r/2) {
			if (l%2 == 0) ans = min(ans, values[l+1]);
			if (r%2 != 0) ans = min(ans, values[r-1]);
			l /= 2, r /= 2;
		}
		return ans;
	}
};

int N; // liczba dzieł sztuki
vector<ll> art_size;
vector<ll> art_value;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	art_size.assign(N, 0);
	art_value.assign(N, 0);

	vector<pair<ll,ll>> vec;

	for (int i=0; i<N; i++) {
		cin >> art_size[i] >> art_value[i];
		vec.push_back({ art_size[i], art_value[i] });
	}

	sort(vec.begin(), vec.end());

	for (int i=0; i<N; i++) {
		art_size[i] = vec[i].first;
		art_value[i] = vec[i].second;
	}

	SegTree_sum sums(art_value);
	SegTree_max maxs(art_size);
	SegTree_min mins(art_size);

	ll ans = art_value[0];

	for (int i=0; i<N; i++) for (int j=i; j<N; j++) {
		ll SUM = sums.Query(i,j);
		ll MAX = maxs.Query(i,j);
		ll MIN = mins.Query(i,j);
		ans = max(ans, SUM - (MAX - MIN));
	}

	cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50