oj.uz

Submission #144065

# Submission time Handle Problem Language Result Execution time Memory
144065 2019-08-15T22:46:53 Z Lawliet Divide and conquer (IZhO14_divide) C++14
17 / 100
 13 ms 2532 KB 
#include <bits/stdc++.h>

#define MAX 100010
#define MAXC 1000000000
#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, int l, int r, int i, lli v)
		{
			if(i < l || r < i) return;

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

				return;
			}

			int 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, int l, int r, int i)
		{
			if(node == 0) return INF;
			if( r < i ) return INF;
			if( i <= l ) return mn[ node ];

			int 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 , -MAXC , MAXC , x[ g ] - se[ g - 1 ] , sg[ g - 1 ]);
		
		lli curAns = SEG.query(1 , -MAXC , MAXC , x[ g ] - se[ g ]);

		curAns = sg[ g ] - curAns;

		ans = max(ans , curAns);
	}

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

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:108: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 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 404 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 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #2
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 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Incorrect 3 ms 760 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1400 KB Output is correct
2 Correct 13 ms 2532 KB Output is correct
3 Incorrect 11 ms 2532 KB Output isn't correct
4 Halted 0 ms 0 KB -