oj.uz

Submission #170938

# Submission time Handle Problem Language Result Execution time Memory
170938 2019-12-26T18:31:34 Z Lightning Divide and conquer (IZhO14_divide) C++14
17 / 100
 96 ms 7672 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) {	
		return tl;
	}
	int tm = (tl + tr) / 2;
	if(t[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) {	
		return t[v];
	}
	int tm = (tl + tr) / 2;
	if(t[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:90: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 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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 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
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 Incorrect 2 ms 380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 9 ms 1272 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 43 ms 4088 KB Output is correct
5 Correct 46 ms 3960 KB Output is correct
6 Correct 96 ms 7644 KB Output is correct
7 Correct 87 ms 7672 KB Output is correct
8 Correct 86 ms 7544 KB Output is correct
9 Correct 86 ms 7648 KB Output is correct
10 Incorrect 81 ms 7672 KB Output isn't correct
11 Halted 0 ms 0 KB -