Submission #162254

#	Time	Username	Problem	Language	Result	Execution time	Memory
162254		mosiashvililuka	Divide and conquer (IZhO14_divide)	C++14	100 / 100	202 ms	21196 KiB

divide

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,zx,xc,fen[200009],jmz[100009],jmx[100009],pas;
pair <pair <long long, long long>, long long> p[100009];
map <long long, long long> m;
map <long long, long long>::iterator it;
long long read(long long q){
	if(q<=0) return 0;
	long long mn=fen[q];
	while(q>0){
		if(mn>fen[q]) mn=fen[q];
		q=q-(q&(-q));
	}
	return mn;
}
void upd(long long q, long long w){
	while(q<=200002){
		if(fen[q]>w) fen[q]=w;
		q=q+(q&(-q));
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(b=1; b<=a; b++){
		cin>>p[b].first.first>>p[b].first.second>>p[b].second;
		swap(p[b].first.second,p[b].second);
		if(pas<p[b].second) pas=p[b].second;
		jmz[b]=p[b].first.second+jmz[b-1];
		jmx[b]=jmx[b-1]+p[b].second;
		p[b].first.first++;
		m[jmz[b-1]-p[b].first.first]=1;
		m[jmz[b]-p[b].first.first]=1;
	}
	c=0;
	for(it=m.begin(); it!=m.end(); it++){
		c++;
		m[(*it).first]=c;
	}
	for(b=0; b<=200005; b++) fen[b]=999999999999999999LL;
	for(b=1; b<=a; b++){
		c=read(m[jmz[b]-p[b].first.first]);
		if(pas<jmx[b]-c) pas=jmx[b]-c;
		upd(m[jmz[b-1]-p[b].first.first],jmx[b-1]);
	}
	cout<<pas;
	return 0;
}

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