oj.uz

Submission #1085740

# Submission time Handle Problem Language Result Execution time Memory
1085740 2024-09-08T15:54:13 Z Sunbae Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 344 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);
	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+n+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

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
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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