Submission #1163714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163714		PieArmy	Divide and conquer (IZhO14_divide)	C++20	100 / 100	158 ms	29368 KiB

divide

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define mid ((left+right)>>1)

const ll inf=ll(2e18)+5;

struct Seg{
	int n;
	vector<ll>tree,lazy;
	void init(int N){
		n=N;
		tree.resize(n<<2,-inf);
		lazy.resize(n<<2,0);
	}
	void push(int node,int left,int right){
		if(lazy[node]==0)return;
		tree[node]+=lazy[node];
		if(left!=right){
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	int l,r;
	ll x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r){
			lazy[node]+=x;
			push(node,left,right);
			return;
		}
		push(node,left,right);
		if(left>r||right<l)return;
		up(node*2,left,mid);
		up(node*2+1,mid+1,right);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int lef,int rig,ll val){
		l=lef;r=rig;x=val;
		up();
	}
	ll qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return -inf;
		push(node,left,right);
		if(left>=l&&right<=r)return tree[node];
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	ll query(int lef,int rig){
		l=lef;r=rig;
		return qu();
	}
};

int n,m;

ll ans=0;
Seg seg;
vector<ll>v;
map<ll,int>mp;
array<ll,3>arr[100023];
ll shift=0;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		ll x,g,d;cin>>x>>g>>d;
		arr[i]={x,g,d};
		if(!mp[x-shift]++){
			v.push_back(x-shift);
		}
		if(!mp[x-d-shift]++){
			v.push_back(x-d-shift);
		}
		shift+=d;
	}
	m=v.size();
	sort(v.begin(),v.end());
	for(int i=0;i<m;i++){
		mp[v[i]]=i;
	}
	seg.init(m);
	shift=0;
	for(int i=0;i<n;i++){
		ll x=arr[i][0],g=arr[i][1],d=arr[i][2];
		ans=max(ans,max(0ll,seg.query(mp[x-d-shift],m-1))+g);
		seg.update(mp[x-shift],mp[x-shift],max(0ll,-seg.query(mp[x-shift],mp[x-shift])));
		seg.update(0,m-1,g);
		shift+=d;
	}
	cout<<ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52