oj.uz

Submission #170954

# Submission time Handle Problem Language Result Execution time Memory
170954 2019-12-26T18:59:36 Z Lightning Divide and conquer (IZhO14_divide) C++14
100 / 100
 96 ms 9976 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx,avx2")

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<" "
#define shown(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
#define int ll

const int szT = (1 << 17) - 1;
const int INF = 1e9;

struct rudina {
	int x, g, e;
} a[szT];

int t[szT * 4];
int add[szT * 4];

void push(int v, int tl, int tr) {
	if(add[v]) {
		t[v] += add[v];
		if(tl < tr) {
			add[v * 2] += add[v];
			add[v * 2 + 1] += add[v];
		}
		add[v] = 0ll;
	}
}

void upd(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		add[v] += x;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, x);
	upd(v * 2 + 1, tm + 1, tr, l, r, x);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int tl, int tr) {
	push(v, tl, tr);
	if(tl == tr) {	
		//show(tl);
		return tl;
	}
	int tm = (tl + tr) / 2;
	if(t[v * 2] + add[v * 2] >= 0ll) return get(v * 2, tl, tm);
	else return get(v * 2 + 1, tm + 1, tr);
}

/*int get2(int v, int tl, int tr) {
	push(v, tl, tr);
	if(tl == tr) {	
		//show(tl);
		return tl;
	}
	int tm = (tl + tr) / 2;
	if(t[v * 2] + add[v * 2] >= 0ll) return get2(v * 2, tl, tm);
	else return get2(v * 2 + 1, tm + 1, tr);
}*/

int n, ans, pref[szT];

main () {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].g >> a[i].e;
		pref[i] = pref[i - 1] + a[i].g;
	}	
	int lastx = 0;
	for(int r = 1; r <= n; ++r) {
		upd(1, 1, n, 1, r, a[r].e);
		if(1 < r) upd(1, 1, n, 1, r - 1, -(a[r].x - lastx));
		int l = get(1, 1, n);			
		//show(l); show(r); show(pref[r] - pref[l - 1]), shown(get2(1, 1, n));
		ans = max(ans, pref[r] - pref[l - 1]); 
		lastx = a[r].x;
	}
	cout << ans;
	return 0;
}

Compilation message

divide.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
17.0 / 17.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 380 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 376 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 376 KB Output is correct

Subtask #2
31.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 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 888 KB Output is correct
12 Correct 6 ms 888 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 8 ms 1144 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 43 ms 4600 KB Output is correct
5 Correct 46 ms 3960 KB Output is correct
6 Correct 96 ms 7672 KB Output is correct
7 Correct 84 ms 7688 KB Output is correct
8 Correct 88 ms 7676 KB Output is correct
9 Correct 84 ms 8312 KB Output is correct
10 Correct 81 ms 7572 KB Output is correct
11 Correct 86 ms 9720 KB Output is correct
12 Correct 88 ms 9976 KB Output is correct