oj.uz

Submission #86759

# Submission time Handle Problem Language Result Execution time Memory
86759 2018-11-27T09:38:52 Z Weak123456 Divide and conquer (IZhO14_divide) C++17
17 / 100
 157 ms 9292 KB 
#include<bits/stdc++.h>
#define P pair<lli, lli>
#define x first
#define y second
#define mp make_pair
using namespace std;
typedef long long int lli;
const lli N=100009, inf=1e16;
lli n, l[N], r[N], b[N], s[N], sg[N];
struct T
{
	lli x, g, e;
};
T a[N];
void Inp()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].g>>a[i].e;
		s[i]=s[i-1]+a[i].e;
		sg[i]=sg[i-1]+a[i].g;
	}
}
void FindL()
{
	a[n+1].x=inf;
	deque<lli> p;
	for(int i=1;i<=n;i++)
	{
		b[i]=b[i-1]-(a[i+1].x-a[i].x)+a[i].e;
	}
	for(int i=0;i<=n;i++)
	{
		while(!p.empty())
		{
			if(b[p.back()]>b[i])
			{
				r[p.back()+1]=i;
				p.pop_back();
			}
			else
			{
				break;
			}
		}
		p.push_back(i);
	}
	r[n]=n;
}
void FindR()
{
	b[n+1]=0;
	a[0].x=-inf;
	for(int i=n;i>=1;i--)
	{
		b[i]=b[i+1]+a[i].e-(a[i].x-a[i-1].x);
	}
	deque<lli> p;
	for(int i=n+1;i>=1;i--)
	{
		while(!p.empty())
		{
			if(b[p.back()]>b[i])
			{
				l[p.back()-1]=i;
				p.pop_back();
			}
			else
			{
				break;
			}
		}
		p.push_back(i);
	}
	l[1]=1;
}
struct T1
{
	lli l, r, x;
};
deque<T1> p, q;
void Fixed()
{
	for(int i=1;i<=n;i++)
	{
		r[i]=a[i].x+s[r[i]]-s[i-1];
		l[i]=a[i].x-(s[i]-s[l[i]-1]);
	}
	lli maxx=-inf, minn=inf;
	for(int i=1;i<=n;i++)
	{
		if(r[i]>maxx)
		{
			maxx=r[i];
			p.push_back({a[i].x, r[i], i});
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(l[i]<minn)
		{
			minn=l[i];
			q.push_front({l[i], a[i].x, i});
		}
	}
}
void Solve()
{
	lli kq=0, s1=p.size(), s2=q.size(), v=0;
	for(int i=0;i<s1;i++)
	{
		while(v<s2)
		{
			if(q[v].l>p[i].r)
			{
				break;
			}
			v++;
		}
		kq=max(kq, sg[q[v-1].x]-sg[p[i].x-1]);
	}
	cout<<kq;
}
int main()
{
	//freopen("test.inp","r",stdin);
	Inp();
	FindL();
	FindR();
	Fixed();
	Solve();
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 544 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Incorrect 3 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 788 KB Output is correct
2 Correct 11 ms 1300 KB Output is correct
3 Correct 13 ms 1300 KB Output is correct
4 Correct 61 ms 4004 KB Output is correct
5 Correct 75 ms 4052 KB Output is correct
6 Correct 157 ms 7332 KB Output is correct
7 Correct 120 ms 7332 KB Output is correct
8 Correct 116 ms 7332 KB Output is correct
9 Correct 117 ms 7496 KB Output is correct
10 Incorrect 117 ms 9292 KB Output isn't correct
11 Halted 0 ms 0 KB -