oj.uz

Submission #144067

# Submission time Handle Problem Language Result Execution time Memory
144067 2019-08-15T22:52:19 Z Lawliet Divide and conquer (IZhO14_divide) C++14
100 / 100
 272 ms 55444 KB 
#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

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.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 5 ms 1016 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 4 ms 1020 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 6 ms 1020 KB Output is correct
11 Correct 14 ms 2276 KB Output is correct
12 Correct 14 ms 2276 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1400 KB Output is correct
2 Correct 18 ms 2404 KB Output is correct
3 Correct 23 ms 3928 KB Output is correct
4 Correct 117 ms 18956 KB Output is correct
5 Correct 107 ms 19116 KB Output is correct
6 Correct 272 ms 55444 KB Output is correct
7 Correct 209 ms 37252 KB Output is correct
8 Correct 206 ms 37352 KB Output is correct
9 Correct 175 ms 20768 KB Output is correct
10 Correct 166 ms 17080 KB Output is correct
11 Correct 212 ms 30204 KB Output is correct
12 Correct 208 ms 30232 KB Output is correct