Submission #68438

#	Time	Username	Problem	Language	Result	Execution time	Memory
68438		ekrem	Divide and conquer (IZhO14_divide)	C++98	100 / 100	300 ms	33916 KiB

divide

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define N 1000005
using namespace std;

typedef long long ll;

ll n, m, ans, a[N], b[N], c[N], suf[N], gol[N], seg[4*N];
pair < ll , ll > mx;
map < ll , ll > h, yer;
map < ll , ll > :: iterator it;

void up(ll k, ll bas, ll son, ll x, ll y){
	if(bas == son){
		seg[k] = min(seg[k], y);
		return;
	}
	if(x <= orta)
		up(sol, bas, orta, x, y);
	else
		up(sag, orta + 1, son, x, y);
	seg[k] = min(seg[sol] , seg[sag]);
}

ll qu(ll k, ll bas, ll son, ll x, ll y){
	if(bas > y or son < x)
		return inf;
	if(bas >= x and son <= y)
		return seg[k];
	return min(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}

void bu(ll k, ll bas, ll son){
	if(bas == son){
		seg[k] = inf;
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = inf;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("outt.txt", "w", stdout);
	scanf("%lld",&n);
	for(ll i = 1; i <= n; i++)
		scanf("%lld %lld %lld",a + i, b + i, c + i);
	for(ll i = n; i >= 1; i--){
		suf[i] = suf[i + 1] + c[i];
		gol[i] = gol[i + 1] + b[i];
		h[suf[i] + a[i] ]++;
		h[suf[i + 1] + a[i] ]++;
	}
	for(it = h.begin(); it != h.end(); it++)
		yer[it->st] = ++m;

	bu(1, 1, m);

	for(ll i = 1; i <= n; i++){
		up(1, 1, m, yer[suf[i] + a[i] ], i);
		ll j = qu(1, 1, m, yer[suf[i + 1] + a[i] ], m);
		ans = max(ans, gol[j] - gol[i + 1]);
		// cout << j << " , " << i << " -> " << gol[j] << " , " << gol[i + 1] << " -> " << ans << endl;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
divide.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",a + i, b + i, c + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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