Submission #1085747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085747		Sunbae	Divide and conquer (IZhO14_divide)	C++17	17 / 100	1018 ms	348 KiB

divide

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
array<int,3> a[N];
ll qs[N], cp[N<<1], QS[N];
int bit[N<<1], m = 0, n;
int pos(int x){ return upper_bound(cp, cp+m, x) - cp;}
void upd(int i, int val){ for(; i<=m; i+=i&-i) bit[i] = min(bit[i], val);}
int qry(int i){ int res = n+1; for(; i; i-=i&-i) res = min(res, bit[i]); return res;}
signed main(){
	scanf("%d", &n);
	for(int i = 1, x, y, z; i<=n; ++i){
		scanf("%d %d %d", &x, &y, &z);
		a[i][0] = x; a[i][1] = y; a[i][2] = z;
	}
	for(int i = 1; i<=n; ++i){
		qs[i] = qs[i-1] + a[i][2];
		QS[i] = QS[i-1] + a[i][1];
		cp[m++] = qs[i] - a[i][0];
		cp[m++] = qs[i-1] - a[i][0];
	}
	sort(cp, cp+m); m = unique(cp, cp+m) - cp;
	ll mx = 0;
	fill(bit, bit+m+1, n+1);
	for(int i = 1; i<=n; ++i){
		upd(pos(qs[i-1] - a[i][0]), i);
		int j = qry(pos(qs[i] - a[i][0]));
		if(j <= n) mx = max(mx, QS[i] - QS[j-1]);
	}
	printf("%lld", mx);
}

Compilation message (stderr)

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

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