Submission #393411

#	Time	Username	Problem	Language	Result	Execution time	Memory
393411		asbsfds	Divide and conquer (IZhO14_divide)	C++14	100 / 100	100 ms	23272 KiB

divide

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const llint inf = (1LL << 60);
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
int x[maxn];
llint g[maxn], d[maxn];
llint tour[treesiz];
llint c[maxn];
vector< llint > v;

void update(int x, llint val) {
	x += off;
	tour[x] = min(tour[x], val);
	
	x /= 2;
	while (x > 0) tour[x] = min(tour[x * 2], tour[x * 2 + 1]), x /= 2;
}

llint query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return inf;
	if (l >= a && r <= b) return tour[node];
	
	int mid = (l + r) / 2;
	return min(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf("%d%lld%lld", x+i, g+i, d+i);
	
	for (int i = 1; i <= n; i++) {
		g[i] += g[i - 1];
		d[i] += d[i - 1];
	}
	for (int i = 1; i < treesiz; i++) tour[i] = inf;
	
	v.push_back(-inf);
	for (int i = 1; i <= n; i++) {
		c[i] = d[i - 1] - x[i];
		v.push_back(c[i]);
	}
	
	//for (int i = 1; i <= n; i++) printf("%lld ", c[i]); printf("\n");
	
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	
	llint sol = 0;
	for (int i = 1; i <= n; i++) {
		sol = max(sol, g[i] - g[i - 1]);
		
		llint ac = d[i] - x[i];
		int ind = upper_bound(v.begin(), v.end(), ac) - v.begin(); ind--;
		sol = max(sol, g[i] - query(0, ind, 0, off - 1, 1));
		
		ind = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
		update(ind, g[i - 1]);
	}
	printf("%lld\n", sol);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
divide.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d%lld%lld", x+i, g+i, d+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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