Submission #1085763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085763		Sunbae	Divide and conquer (IZhO14_divide)	C++17	100 / 100	37 ms	6228 KiB

divide

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 100001;
int a[N], m = 0, n, bit[N];
ll b[N], c[N], cp[N];
inline int pos(ll x){ return upper_bound(cp, cp+m, x) - cp;}
int qry(int i){ int res = n+1; for(; i; i-=i&-i) res = min(res, bit[i]); return res;}
void upd(int i, int v){ for(; i<=m; i+=i&-i) bit[i] = min(bit[i], v);}

signed main(){
	scanf("%d", &n);
	for(int i = 1; i<=n; ++i){
		scanf("%d %lld %lld", a+i, b+i, c+i);
		b[i] += b[i-1]; c[i] += c[i-1];
		cp[m++] = c[i-1] - a[i];
	}
	sort(cp, cp+m); m = unique(cp, cp+m) - cp;
	fill(bit, bit+m+1, n+1);
	ll mx = 0;
	for(int i = 1; i<=n; ++i){
		upd(pos(c[i-1] - a[i]), i);
		int j = qry(pos(c[i] - a[i]));
		if(j <= n) mx = max(mx, b[i] - b[j-1]);
	}
	printf("%lld", mx);
}

Compilation message (stderr)

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

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