oj.uz

Submission #131129

# Submission time Handle Problem Language Result Execution time Memory
131129 2019-07-16T16:09:31 Z maruii Divide and conquer (IZhO14_divide) C++14
17 / 100
 5 ms 1016 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int SIZE = 1 << 10;
struct ST {
	int V[2 * SIZE];
	void update(int x, int v) {
		for (x += SIZE; x; x >>= 1) V[x] = max(V[x], v);
	}
	int query(int s, int e) {
		int ret = 0;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, V[s++]);
			if (~e & 1) ret = max(ret, V[e--]);
		}
		return ret;
	}
} seg;

int X[100005];
ll G[100005], D[100005];
vector<ll> xx;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i] >> G[i] >> D[i];
		G[i] += G[i - 1];
		D[i] += D[i - 1];
		xx.push_back(D[i] - X[i]);
	}
	sort(xx.begin(), xx.end()); xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) seg.update(lower_bound(xx.begin(), xx.end(), D[i] - X[i]) - xx.begin(), i);
	ll ans = 0;
	for (int i = 1; i <= N; ++i) ans = max(ans, G[seg.query(lower_bound(xx.begin(), xx.end(), D[i - 1] - X[i]) - xx.begin(), xx.size())] - G[i - 1]);
	cout << ans;
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -