Submission #344605

#	Time	Username	Problem	Language	Result	Execution time	Memory
344605		maskoff	Divide and conquer (IZhO14_divide)	C++14	100 / 100	160 ms	26988 KiB

divide

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

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

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

struct pt{
 	ll x, g, d;
};

vector<pt> a(N);
vector<ll> pref(N), opt(N);

struct tree{
 	ll mx;
 	ll tag;
} t[N];

void build(int u, int l, int r) {
 	if (l == r) {
 	 	t[u].mx = a[l].x;
 	 	return;
 	}
 	int m = l + r >> 1;
 	build(u + u, l, m);
 	build(u + u + 1, m + 1, r);
 	t[u].mx = min(t[u + u].mx, t[u + u + 1].mx);
}

void push(int u, int l, int r) {
 	if (l == r || t[u].tag == 0) return;
 	t[u + u].mx += t[u].tag;
 	t[u + u + 1].mx += t[u].tag;
 	t[u + u + 1].tag += t[u].tag;
 	t[u + u].tag += t[u].tag;
 	t[u].tag = 0;
 	return;
}

void update(int u, int ul, int ur, int l, int r, int val) {
	push(u, ul, ur);
 	if (ul > r || l > ur) return;
 	if (l <= ul && ur <= r) {
 		t[u].mx += val;
 		t[u].tag += val;
 	 	return;
	}
	int um = ul + ur >> 1;
	update(u + u, ul, um, l, r, val);
	update(u + u + 1, um + 1, ur, l, r, val);
	t[u].mx = min(t[u + u].mx, t[u + u + 1].mx);
}

int get(int u, int ul, int ur, int l, int r) {
	push(u, ul, ur);
 	if (ul > r || l > ur || t[u].mx > 0) return -1;
 	if (ul == ur) return ul;
 	int um = ul + ur >> 1;
 	int res = get(u + u + 1, um + 1, ur, l, r);
 	if (res == -1) res = get(u + u, ul, um, l, r);
 	return res;
}


ll calc(int l, int r) {
	if (l == -1 || r == -1) return -1;
 	return pref[r] - pref[l - 1];
}


int main() {   
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	int n;
	cin >> n;
	ll mx = 0;
	for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].g >> a[i].d, mx = max(mx, (ll)a[i].g); 
	for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i].g;
	build(1, 1, n);
	for (int i = n; i >= 1; i--) {
		update(1, 1, n, i + 1, n, -a[i].x);
		update(1, 1, n, i, n, -a[i].d);
		opt[i] = get(1, 1, n, i, n);
		//cout << i << " " << opt[i] << endl;
		update(1, 1, n, i + 1, n, +a[i].x);
	}
	for (int i = 1; i <= n; i++) 
	 	mx = max(mx, calc(i, opt[i]));
	cout << mx << endl;
  return 0;              
}

Compilation message (stderr)

divide.cpp: In function 'void build(int, int, int)':
divide.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int m = l + r >> 1;
      |           ~~^~~
divide.cpp: In function 'void update(int, int, int, int, int, int)':
divide.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |  int um = ul + ur >> 1;
      |           ~~~^~~~
divide.cpp: In function 'int get(int, int, int, int, int)':
divide.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int um = ul + ur >> 1;
      |            ~~~^~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52