oj.uz

Submission #114164

# Submission time Handle Problem Language Result Execution time Memory
114164 2019-05-31T04:48:44 Z jwvg0425 코알라 (JOI13_koala) C++17
30 / 100
 219 ms 262144 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <iterator>
#include <chrono>
#define MOD 1000000007
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }

template<typename T, typename Merge>
class SegmentTree
{
public:
	SegmentTree(Merge m)
		:merge(m) {}

	void init(vector<T>& raw_)
	{
		raw = raw_;
		n = (int)raw.size();
		int sz = (1 << (clog2(n) + 1));
		data.resize(sz);

		_init(raw, 1, 0, n - 1);
	}

	T modify(int idx, function<T(T)> modifier) { return update(idx, modifier(raw[idx])); }
	T update(int idx, const T& newVal) { raw[idx] = newVal; return _update(1, 0, n - 1, idx, newVal); }
	T query(int left, int right) { return _query(1, 0, n - 1, left, right); }

private:
	vector<T> raw;
	vector<T> data;
	int n;
	Merge merge;

	T _init(vector<T>& raw, int node, int start, int end)
	{
		int mid = (start + end) / 2;
		if (start == end)
			return data[node] = raw[start];
		else
			return data[node] = merge(_init(raw, node * 2, start, mid),
				_init(raw, node * 2 + 1, mid + 1, end));
	}

	T _update(int node, int start, int end, int index, const T& newVal)
	{
		if (index < start || index > end)
			return data[node];

		if (start == end)
			data[node] = newVal;
		else
		{
			int mid = (start + end) / 2;
			data[node] = merge(_update(node * 2, start, mid, index, newVal),
				_update(node * 2 + 1, mid + 1, end, index, newVal));
		}

		return data[node];
	}

	T _query(int node, int start, int end, int left, int right)
	{
		if (left <= start && end <= right)
			return data[node];

		int mid = (start + end) / 2;

		if (mid < left)
			return _query(node * 2 + 1, mid + 1, end, left, right);

		if (mid + 1 > right)
			return _query(node * 2, start, mid, left, right);

		return merge(_query(node * 2, start, mid, left, right),
			_query(node * 2 + 1, mid + 1, end, left, right));
	}
};

template<typename T, typename Merge>
SegmentTree<T, Merge> segTree(Merge merge)
{
	return SegmentTree<T, Merge>(merge);
}

i64 d, a;
i64 b[100005];
i64 pos[100005];



int main()
{
	i64 k, m, n;
	scanf("%lld %lld %lld %lld %lld", &k, &m, &d, &a, &n);

	pos[0] = k;
	pos[n + 1] = m;

	for (int i = 1; i <= n; i++)
		scanf("%lld %lld", &pos[i], &b[i]);

	auto maxTree = segTree<i64>([](const i64& l, const i64& r) { return max(l, r); });

	auto value = vector<i64>(d + 1, -(1ll << 60));
	value[d] = 0;

	maxTree.init(value);

	for (int i = 1; i <= n + 1; i++)
	{
		i64 dist = (pos[i] - k + d - 1) / d * a;
		i64 di = (pos[i] - k) % d;
		if (di == 0)
			di = d;

		auto dl = maxTree.query(0, di - 1) - a;
		auto dr = maxTree.query(di, d);

		value[di] = max(dl, dr) + b[i];
		maxTree.update(di, value[di]);
	}

	auto lastd = (pos[n + 1] - k) % d;

	if (lastd == 0)
		lastd = d;

	printf("%lld\n", value[lastd] - (pos[n + 1] - k + d - 1) / d * a);

	return 0;
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:136:7: warning: unused variable 'dist' [-Wunused-variable]
   i64 dist = (pos[i] - k + d - 1) / d * a;
       ^~~~
koala.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld %lld", &k, &m, &d, &a, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &pos[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2168 KB Output is correct
2 Correct 37 ms 1996 KB Output is correct
3 Correct 20 ms 1536 KB Output is correct
4 Correct 39 ms 2072 KB Output is correct
5 Correct 23 ms 1400 KB Output is correct
6 Correct 15 ms 1024 KB Output is correct
7 Correct 27 ms 2048 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 5676 KB Output is correct
2 Correct 155 ms 35952 KB Output is correct
3 Runtime error 219 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -