oj.uz

Submission #114165

# Submission time Handle Problem Language Result Execution time Memory
114165 2019-05-31T04:54:53 Z jwvg0425 코알라 (JOI13_koala) C++17
100 / 100
 177 ms 16120 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);
}

class Mapping
{
public:
	void init(const vector<i64>& raw, int base = 0)
	{
		start = base;
		arr = raw;
		sort(arr.begin(), arr.end());
		arr.erase(unique(arr.begin(), arr.end()), arr.end());

		for (int i = 0; i < arr.size(); i++)
			idx[arr[i]] = base + i;
	}

	int get_idx(i64 k)
	{
		return idx[k];
	}

	i64 get_value(int idx)
	{
		return arr[idx - start];
	}

	int size() const
	{
		return arr.size();
	}

private:
	int start;
	vector<i64> arr;
	map<i64, int> idx;
};

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]);

	vector<i64> dvalue(n + 2);
	
	for (int i = 0; i <= n + 1; i++)
	{
		dvalue[i] = (pos[i] - k) % d;
		if (dvalue[i] == 0)
			dvalue[i] = d;
	}

	Mapping mapping;
	mapping.init(dvalue, 1);

	vector<i64> dmap(n + 2);

	for (int i = 0; i <= n + 1; i++)
		dmap[i] = mapping.get_idx(dvalue[i]);

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

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

	maxTree.init(value);

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

		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]);
	}

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

	return 0;
}

Compilation message

koala.cpp: In member function 'void Mapping::init(const std::vector<long long int>&, int)':
koala.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < arr.size(); i++)
                   ~~^~~~~~~~~~~~
koala.cpp: In function 'int main()':
koala.cpp:186:7: warning: unused variable 'dist' [-Wunused-variable]
   i64 dist = (pos[i] - k + d - 1) / d * a;
       ^~~~
koala.cpp:152: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:158: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7900 KB Output is correct
2 Correct 64 ms 7964 KB Output is correct
3 Correct 34 ms 4992 KB Output is correct
4 Correct 63 ms 7828 KB Output is correct
5 Correct 39 ms 4684 KB Output is correct
6 Correct 24 ms 3328 KB Output is correct
7 Correct 47 ms 7808 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 11768 KB Output is correct
2 Correct 177 ms 13944 KB Output is correct
3 Correct 175 ms 16120 KB Output is correct
4 Correct 131 ms 16092 KB Output is correct
5 Correct 104 ms 9720 KB Output is correct
6 Correct 75 ms 7416 KB Output is correct