oj.uz

Submission #167800

# Submission time Handle Problem Language Result Execution time Memory
167800 2019-12-10T07:44:31 Z Gurban Divide and conquer (IZhO14_divide) C++11
100 / 100
 307 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(ll 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(ll 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);
		upd(x + e,i,i,1,n,1);
		pos = tap(x,1,n,1);
		mx = max(go[i] - go[pos - 1],mx);
	}
	cout << mx;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 5 ms 508 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 16 ms 1144 KB Output is correct
12 Correct 15 ms 1144 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Correct 20 ms 1784 KB Output is correct
3 Correct 24 ms 1912 KB Output is correct
4 Correct 123 ms 7008 KB Output is correct
5 Correct 144 ms 7192 KB Output is correct
6 Correct 307 ms 14328 KB Output is correct
7 Correct 234 ms 13176 KB Output is correct
8 Correct 239 ms 13240 KB Output is correct
9 Correct 227 ms 13004 KB Output is correct
10 Correct 225 ms 13056 KB Output is correct
11 Correct 256 ms 13688 KB Output is correct
12 Correct 266 ms 13776 KB Output is correct