oj.uz

Submission #48649

# Submission time Handle Problem Language Result Execution time Memory
48649 2018-05-17T16:06:44 Z rkocharyan Divide and conquer (IZhO14_divide) C++14
100 / 100
 247 ms 58672 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <bitset>
#include <iomanip>
#include <memory>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cassert>
using namespace std;

#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define mp make_pair
#define add push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(a,b) memset(a, b, sizeof(a))
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:20000007")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> lnum;

const int N = (int)1e6 + 100;
const int maxn = (int)1e3 + 100;
const int base = (int)1e9;
const int mod = (int)1e9 + 7;
const int inf = INT_MAX;
const long long ll_inf = LLONG_MAX;
const long double PI = acos((long double)-1.0);
const long double eps = 1e-8;

long long T[4 * N];

void update(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		T[v] = min(T[v], 1LL * val);
	}
	else {
		int tm = (tl + tr) >> 1;
		if (pos <= tm) update(2 * v + 1, tl, tm, pos, val);
		else update(2 * v + 2, tm + 1, tr, pos, val);
		T[v] = min(T[2 * v + 1], T[2 * v + 2]);
	}
}

long long query(int v, int tl, int tr, int l, int r) {
	if (l > r) return inf;
	if (tl == l && tr == r) return T[v];
	int tm = (tl + tr) >> 1;
	return min(query(2 * v + 1, tl, tm, l, min(r, tm)),
		query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r));
}

void solve() {
	memset(T, 32, sizeof T);
	int n; cin >> n;
	vector <long long> diff;
	vector <int> X(n), G(n), E(n);
	vector <long long> pg(n, 0), pe(n, 0);
	for (int i = 0; i < n; ++i) {
		cin >> X[i] >> G[i] >> E[i];
		pe[i] = E[i];
		pg[i] = G[i];
		if (i) pe[i] += pe[i - 1], pg[i] += pg[i - 1];
		if (i) diff.add(X[i] - pe[i - 1]);
		else diff.add(X[0]);
	}
	set <int> sdiff;
	for (int i = 0; i < n; ++i) sdiff.insert(diff[i]);
	diff.clear();
	for (int i : sdiff) diff.add(i);
	for (int i = 0; i < n; ++i) {
		int it = 0;
		if (i) it = lower_bound(all(diff), X[i] - pe[i - 1]) - diff.begin();
		else it = lower_bound(all(diff), X[0]) - diff.begin();
		update(0, 0, n, it, i);
	}
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int it = lower_bound(all(diff), X[i] - pe[i]) - diff.begin();
		it = query(0, 0, n, it, n);
		if (it < n) ans = max(ans, pg[i] - (it == 0 ? 0 : pg[it - 1]));
	}
	cout << ans << '\n';
}

int main() {
	//ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	//#define Freopen
#ifdef Freopen
#ifndef _MSC_VER 
#define TASK ""
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
#endif

	int T = 1;
	//scanf("%d", &T);

	for (; T; --T) solve();

#ifdef DEBUG
	cerr << double(1.0 * clock() / CLOCKS_PER_SEC) << '\n';
#endif 

	return 0;
}

Compilation message

divide.cpp:31:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 
divide.cpp:32:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:20000007")

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31736 KB Output is correct
2 Correct 25 ms 31860 KB Output is correct
3 Correct 26 ms 31900 KB Output is correct
4 Correct 25 ms 31964 KB Output is correct
5 Correct 27 ms 31964 KB Output is correct
6 Correct 26 ms 31964 KB Output is correct
7 Correct 27 ms 32068 KB Output is correct
8 Correct 26 ms 32092 KB Output is correct
9 Correct 37 ms 32196 KB Output is correct
10 Correct 26 ms 32196 KB Output is correct
11 Correct 26 ms 32196 KB Output is correct
12 Correct 26 ms 32272 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32276 KB Output is correct
2 Correct 25 ms 32284 KB Output is correct
3 Correct 25 ms 32288 KB Output is correct
4 Correct 26 ms 32384 KB Output is correct
5 Correct 28 ms 32464 KB Output is correct
6 Correct 27 ms 32508 KB Output is correct
7 Correct 28 ms 32540 KB Output is correct
8 Correct 39 ms 32576 KB Output is correct
9 Correct 27 ms 32596 KB Output is correct
10 Correct 28 ms 32756 KB Output is correct
11 Correct 33 ms 33044 KB Output is correct
12 Correct 34 ms 33156 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33296 KB Output is correct
2 Correct 38 ms 33872 KB Output is correct
3 Correct 40 ms 34004 KB Output is correct
4 Correct 101 ms 38516 KB Output is correct
5 Correct 113 ms 39780 KB Output is correct
6 Correct 247 ms 46896 KB Output is correct
7 Correct 187 ms 48624 KB Output is correct
8 Correct 185 ms 50708 KB Output is correct
9 Correct 240 ms 52344 KB Output is correct
10 Correct 241 ms 54084 KB Output is correct
11 Correct 235 ms 56564 KB Output is correct
12 Correct 234 ms 58672 KB Output is correct