oj.uz

Submission #167786

# Submission time Handle Problem Language Result Execution time Memory
167786 2019-12-10T06:33:49 Z Gurban Divide and conquer (IZhO14_divide) C++11
0 / 100
 303 ms 14328 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ss second
#define ff first
#define N 100005
#define inf 1000000009
#define ll long long
#define mid(a,b) (a+b)/2

using namespace std;

int n,pos;
ll T[4 * N][5],x,g,e,go[N],mx;

void upd(int val,int a,int b,int l,int r,int nd){
	T[nd][0] += T[nd / 2][1];
	T[nd][1] += T[nd / 2][1];
	if(l >= a and r <= b){
		T[nd][0] += val;
		T[nd][1] += val;
		return;
	}
	if(l > b or r < a)
		return;
	upd(val,a,b,l,mid(l,r),nd * 2);
	upd(val,a,b,mid(l,r) + 1,r,nd * 2 + 1);
	T[nd][1] = 0;
	T[nd][0] = max(T[nd * 2][0],T[nd * 2 + 1][0]);
}
int tap(int x,int l,int r,int nd){
	if(l == r)
		return l;
	T[nd * 2][0] += T[nd][1];
	T[nd * 2][1] += T[nd][1];
	T[nd * 2 + 1][0] += T[nd][1];
	T[nd * 2 + 1][1] += T[nd][1];
	T[nd][1] = 0;
	if(T[nd * 2][0] >= x)
		return tap(x,l,mid(l,r),nd * 2);
	return tap(x,mid(l,r) + 1,r,nd * 2 + 1);
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> x >> g >> e;
		go[i] = go[i - 1] + g;
		upd(e,1,i - 1,1,n,1);
		pos = tap(x,1,n,1);
		upd(x+e,i,i,1,n,1);
		mx = max(go[i] - go[pos - 1],mx);
	}	
	cout << mx;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct
2 Correct 20 ms 1692 KB Output is correct
3 Correct 24 ms 1912 KB Output is correct
4 Correct 123 ms 6820 KB Output is correct
5 Correct 139 ms 6888 KB Output is correct
6 Correct 303 ms 14328 KB Output is correct
7 Correct 229 ms 12512 KB Output is correct
8 Correct 239 ms 12920 KB Output is correct
9 Correct 226 ms 12920 KB Output is correct
10 Incorrect 231 ms 12976 KB Output isn't correct
11 Halted 0 ms 0 KB -