Submission #144067

#	Time	Username	Problem	Language	Result	Execution time	Memory
144067		Lawliet	Divide and conquer (IZhO14_divide)	C++14	100 / 100	272 ms	55444 KiB

divide

#include <bits/stdc++.h>

#define MAX 100010
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;

class SparseSegmentTree
{
	public:

		void build()
		{
			e.push_back( 0 );
			d.push_back( 0 );

			mn.push_back( INF );
		}

		int getLeft(int node)
		{
			if(e[node] == 0)
			{
				e[node] = ++curNode;
				build();
			}

			return e[node];
		}

		int getRight(int node)
		{
			if(d[node] == 0)
			{
				d[node] = ++curNode;
				build();
			}

			return d[node];
		}

		void update(int node, lli l, lli r, lli i, lli v)
		{
			if(i < l || r < i) return;

			if(l == r)
			{
				mn[ node ] = min(mn[ node ] , v);

				return;
			}

			lli m = (l + r)/2;
			if(l == r - 1) m = l;

			if(i <= m) update(getLeft(node) , l , m , i , v);
			else update(getRight(node) , m + 1 , r , i , v);

			mn[ node ] = min(mn[ e[node] ] , mn[ d[node] ]);
		}

		lli query(int node, lli l, lli r, lli i)
		{
			if(node == 0) return INF;
			if( r < i ) return INF;
			if( i <= l ) return mn[ node ];

			lli m = (l + r)/2;
			if(l == r - 1) m = l;

			lli mnLeft = query(e[node] , l , m , i);
			lli mnRight = query(d[node] , m + 1 , r , i);

			return min(mnLeft , mnRight);
		}

		SparseSegmentTree() : curNode( 1 ) { build(); build(); }

	private:

		int curNode;

		vector<int> e, d;
		vector<lli> mn;
};

int n;

int x[MAX];
int gold[MAX];
int energy[MAX];

lli ans;

lli sg[MAX];
lli se[MAX];

SparseSegmentTree SEG;

int main()
{
	scanf("%d",&n);

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d %d",&x[g],&gold[g],&energy[g]);

		sg[ g ] = sg[ g - 1 ] + gold[g];
		se[ g ] = se[ g - 1 ] + energy[g];
	}

	for(int g = 1 ; g <= n ; g++)
	{
		SEG.update(1 , -INF , INF , x[ g ] - se[ g - 1 ] , sg[ g - 1 ]);

		lli curAns = SEG.query(1 , -INF , INF , x[ g ] - se[ g ]);

		ans = max(ans , sg[ g ] - curAns);
	}

	printf("%lld\n",ans);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x[g],&gold[g],&energy[g]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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