Submission #167800

#	Time	Username	Problem	Language	Result	Execution time	Memory
167800		Gurban	Divide and conquer (IZhO14_divide)	C++11	100 / 100	307 ms	14328 KiB

divide

#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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52