oj.uz

Submission #170925

# Submission time Handle Problem Language Result Execution time Memory
170925 2019-12-26T18:11:42 Z Lightning Divide and conquer (IZhO14_divide) C++14
17 / 100
 10 ms 1400 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 <<"\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];

pii t[szT * 3];
int add[szT * 3];

void build(int v, int tl, int tr) {
	if(tl == tr) {
		t[v].S = tl;
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}


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

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 t[v].S;
	}
	int tm = (tl + tr) / 2;
	if(t[v * 2].F >= 0) return get(v * 2, tl, tm);
	else return get(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;
	}	
	build(1, 1, n);
	int lastr = a[1].x;
	for(int r = 1; r <= n; ++r) {
		upd(1, 1, n, 1, r - 1, a[r].e - (a[r].x - lastr));
		upd(1, 1, n, r, r, a[r].e);
		int l = get(1, 1, n);			
		ans = max(ans, pref[r] - pref[l - 1]); 
		lastr = a[r].x;
	}
	cout << ans;
	return 0;
}

Compilation message

divide.cpp:91: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 380 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 424 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 380 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 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 10 ms 1272 KB Output is correct
3 Incorrect 10 ms 1400 KB Output isn't correct
4 Halted 0 ms 0 KB -