제출 #392600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392600		vanic	금 캐기 (IZhO14_divide)	C++14	100 / 100	168 ms	7128 KiB

divide

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <array>

using namespace std;

typedef long long ll;
const int maxn=1e5+5, Log=17, pot=(1<<Log);

struct tournament{
	ll t[pot*2], prop[pot*2];
	void propagate(int x){
		if(!prop[x]){
			return;
		}
		t[x]+=prop[x];
		if(x<pot){
			prop[x*2]+=prop[x];
			prop[x*2+1]+=prop[x];
		}
		prop[x]=0;
	}
	void update(int x, int val){
		t[x]+=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	void update2(int L, int D, int x, int l, int d, int val){
		propagate(x);
		if(L>=l && D<=d){
//			cout << "na " << L << ' ' << D << endl;
			update(x, val);
			if(x<pot){
				prop[x*2]+=val;
				prop[x*2+1]+=val;
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
	int query(int x){
//		cout <<  x << ' ' << t[x] << endl;
		if(x>=pot){
			return x;
		}
		propagate(x*2);
		propagate(x*2+1);
		if(t[x*2]<=0){
			return query(x*2);
		}
		return query(x*2+1);
	}
};
/*
struct logaritamska{
	ll l[maxn];
	void update(int x, int val){
		for(; x<maxn; x+=(x & -x)){
			l[x]+=val;
		}
	}
	ll query(int x){
		ll sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};

inline int rev(int x){
	return maxn-x-1;
}

logaritamska L;*/

tournament T;
int l[maxn][3];
ll pref[maxn];
/*
int binary(int x){
	int lo=0, hi=x, mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(L.query(rev(mid))>0){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}*/

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> l[i][0] >> l[i][1] >> l[i][2];
		pref[i+1]=pref[i]+l[i][1];
	}
	int pos;
	ll val=0;
	for(int i=0; i<n; i++){
		T.update2(0, pot-1, 1, 0, i, -l[i][2]);
		if(i){
			T.update2(0, pot-1, 1, 0, i-1, l[i][0]-l[i-1][0]);
		}
		pos=T.query(1)-pot;
		val=max(val, pref[i+1]-pref[pos]);
//		cout << i  <<  ' ' << pos <<  endl;
	}
	cout << val << '\n';
	return 0;
}

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