oj.uz

Submission #1085723

# Submission time Handle Problem Language Result Execution time Memory
1085723 2024-09-08T15:43:20 Z Sunbae Divide and conquer (IZhO14_divide) C++17
0 / 100
 0 ms 348 KB 
#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);
	ll mx = 0;
	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;
		mx = max(mx, (ll)y);
	}
	sort(a+1, a+1+n);
	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;
	fill(bit, bit+n+1, n+1);
	for(int i = 1; i<=n; ++i){
		int j = qry(pos(qs[i] - a[i][0]));
		if(j <= n) mx = max(mx, QS[i] - QS[j-1]);
		upd(pos(qs[i-1] - a[i][0]), i);
	}
	printf("%lld", mx);
}

Compilation message

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:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -