Submission #282015

#	Time	Username	Problem	Language	Result	Execution time	Memory
282015		FlashGamezzz	Art Exhibition (JOI18_art)	C++17	100 / 100	653 ms	37588 KiB

art

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
using namespace std;

long n;
long long maxa[1100000] = {}, upd[1100000] = {};
void updf(long i, long s, long e, long l, long u, long long d) {
	if (upd[i] != 0) {
		maxa[i] += upd[i];
		if (s != e) {
			upd[i * 2 + 1] += upd[i];
			upd[i * 2 + 2] += upd[i];
		}
		upd[i] = 0;
	}
	if (s > e || s > u || e < l) {
		return;
	}
	if (s >= l && e <= u) {
		maxa[i] += d;
		if (s != e) {
			upd[i * 2 + 1] += d;
			upd[i * 2 + 2] += d;
		}
		return;
	}
	updf(i * 2 + 1, s, (s + e)/2, l, u, d);
	updf(i * 2 + 2, (s + e)/2 + 1, e, l, u, d);
	maxa[i] = max(maxa[i * 2 + 1], maxa[i * 2 + 2]);
}
void updh(long l, long u, long long d) {
	long a = 0, b = 0;
	updf(a, b, n-1, l, u, d);
}
long long maxf(long i, long s, long e, long l, long u) {
	if (upd[i] != 0) {
		maxa[i] += upd[i];
		if (s != e) {
			upd[i * 2 + 1] += upd[i];
			upd[i * 2 + 2] += upd[i];
		}
		upd[i] = 0;
	}
	if (s > e || s > u || e < l) {
		return -1000;
	}
	if (s >= l && e <= u) {
		return maxa[i];
	}
	return max(maxf(2*i+1, s, (s+e)/2, l, u), maxf(2*i+2, (s+e)/2+1, e, l, u));
}
long long maxh(long l, long u) {
	long a = 0, b = 0;
	return maxf(a, b, n-1, l, u);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	vector< pair <long long,long> > vect;
	for (int i = 0; i < n; i++) {
		long long a;
		long b;
		cin >> a >> b;
		vect.push_back( make_pair(a, b) );
	}
	sort(vect.begin(), vect.end());
	long a = 0;
	pair<long long, long> tp = vect[0];
	long long size = tp.first, ans = 0;
	updh(a, a, (long long) tp.second);
	for (int i = 1; i < n; i++) {
		tp = vect[i];
		updh(a, i-1, size-tp.first);
		updh(a, i, tp.second);
		long long m = maxh(a, i);
		ans = max(ans, m);
		size = tp.first;
	}
	cout << ans;
}

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