oj.uz

Submission #1088654

# Submission time Handle Problem Language Result Execution time Memory
1088654 2024-09-14T17:58:45 Z xnqs Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 3420 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Incorrect 1 ms 3420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Incorrect 1 ms 3420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Incorrect 1 ms 3420 KB Output isn't correct
3 Halted 0 ms 0 KB -