Submission #1088654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088654		xnqs	Divide and conquer (IZhO14_divide)	C++17	0 / 100	1 ms	3420 KiB

divide

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <cstring>

int x;
int diff_coords[100005];
int64_t pfx1[100005];
int64_t pfx2[100005];
int pfx_norm[100005];
int64_t tree[400005];

void normalize() {
	std::map<int64_t,int> map;
	for (int i = 0; i <= x; i++) {
		map[pfx1[i]] = 0;
	}

	int cnt = 0;
	for (auto& i : map) {
		i.second = cnt++;
	}

	for (int i = 0; i <= x; i++) {
		pfx_norm[i] = map[pfx1[i]];
	}
}

void update(int node, int l, int r, int pos, int64_t val) {
	if (l==r) {
		tree[node] = std::min(tree[node],val);
		return;
	}

	int m = (l+r)>>1;
	if (pos<=m) {
		update(node<<1,l,m,pos,val);
	}
	else {
		update(node<<1|1,m+1,r,pos,val);
	}
	tree[node] = std::min(tree[node<<1],tree[node<<1|1]);
}

int64_t query(int node, int l, int r, int st, int fi) {
	if (l>fi||r<st) {
		return 0x3f3f3f3f3f3f3f3fLL;
	}
	if (st<=l&&r<=fi) {
		return tree[node];
	}

	int m = (l+r)>>1;
	return std::min(query(node<<1,l,m,st,fi),query(node<<1|1,m+1,r,st,fi));
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x;
	for (int i = 1; i <= x; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		diff_coords[i] = a - diff_coords[i-1];
		pfx1[i] = pfx1[i-1] + c - diff_coords[i];
		pfx2[i] = pfx2[i-1] + b;
	}

	normalize();

	int64_t ans = 0;
	memset(tree,0x3f,sizeof(tree));
	update(1,0,x,pfx_norm[0],0);
	for (int i = 1; i <= x; i++) {
		ans = std::max(ans,pfx2[i]-pfx2[i-1]);
		ans = std::max(ans,pfx2[i]-query(1,0,x,0,pfx_norm[i]));
		update(1,0,x,pfx_norm[i],pfx2[i]);
	}

	std::cout << ans << "\n";
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52