oj.uz

Submission #213176

# Submission time Handle Problem Language Result Execution time Memory
213176 2020-03-25T06:46:42 Z islingr Divide and conquer (IZhO14_divide) C++14
0 / 100
 5 ms 384 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define ff first
#define ss second

using ll = int64_t;

template<class T> bool ckmin(T &a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1 << 17;
const int inf = 1e9;
int t[N << 1];

int n;
int query(int l, int r) {
	int res = inf;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) ckmin(res, t[l++]);
		if (r & 1) ckmin(res, t[--r]);
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	vector<ll> x(n), g(n + 1), e(n + 1), diff(n);
	rep(i, 0, n) {
		cin >> x[i] >> g[i + 1] >> e[i + 1];
		g[i + 1] += g[i];
		e[i + 1] += e[i];
		diff[i] = x[i] - e[i];
	}
	rep(i, 0, n) t[i + n] = i;
	sort(t + n, t + 2 * n, [&](int a, int b) { return diff[a] < diff[b]; });
	sort(all(diff));

	ll ans = 0;
	rep(i, 0, n) {
		// Find smallest j such that x[j] - e[j] >= x[i] - e[i + 1] 
		
		int k = lb(all(diff), x[i] - e[i + 1]) - begin(diff);
		// [k, n) are the elements such that diff[k] >= x[i] - e[i + 1]
		// find smallest j in [k, n) in segtree 
		int j = query(k, n);
		// for (; j < i; ++j)
		// 	if (x[i] - e[i + 1] <= diff[j])
		// 		break;
		ckmax(ans, g[i + 1] - g[j]);
	}
	cout << ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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